朴素版

#include<bits/stdc++.h>

using namespace std;

const int N=510,M=1e5+10,INF=0x3f3f3f3f;
int idx,e[M],w[M],ne[M],h[N];
int dist[N];
bool st[N];
int n,m;

void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

void dijkstra()
{
    memset(dist,INF,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
        }
        st[t]=true;
        for(int j=h[t];j!=-1;j=ne[j])
        {
            int a=e[j];
            if(dist[a]>dist[t]+w[j]) dist[a]=dist[t]+w[j];
        }
    }
    if(dist[n]==INF) cout<<"-1"<<endl;
    else cout<<dist[n]<<endl;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,e;
        cin>>a>>b>>e;
        add(a,b,e);
    }
    dijkstra();
    return 0;
}

堆优化

#include<bits/stdc++.h>

using namespace std;

const int N=510,M=1e5+10,INF=0x3f3f3f3f;
int idx,e[M],w[M],ne[M],h[N];
int dist[N];
bool st[N];
int n,m;

typedef pair<int,int>PII;

void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

void dijkstra()
{
    memset(dist,INF,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({0,1});
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second,distance=t.first;
        for(int j=h[ver];j!=-1;j=ne[j])
        {
            int a=e[j];
            if(dist[a]>distance+w[j]) 
            {
                dist[a]=distance+w[j];
                heap.push({dist[a],a});
            }
        }
    }
    if(dist[n]==INF) cout<<"-1"<<endl;
    else cout<<dist[n]<<endl;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dijkstra();
    return 0;
}