链式前向星

好像必须u=-1，u=0的话会wa

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int h[N],e[N],ne[N],w[N],idx;
int d[N],vis[N];
int n,m;
 void add(int a,int b,int c)
 {
     e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
 }
void dijkstra(int s)
{
    for(int i=1;i<=n;i++)d[i]=INF;
    d[s]=0;
    for(int i=1;i<n;i++){
        int u=-1;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&(u==-1||d[u]>d[j]))u=j;
        vis[u]=1;
        for(int j=h[u];j!=-1;j=ne[j]){
            int t=e[j];
            d[t]=min(d[t],d[u]+w[j]);
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dijkstra(1);
    int t=d[n];
    if(t==INF)cout<<-1;
    else cout<<t;
    return 0;
}

vector模拟

#include<bits/stdc++.h>
using namespace std;
const int N=1010,INF=0x3f3f3f3f;
struct edge{
    int v,w;
};
vector<edge>e[N];
int d[N],vis[N];
int n,m;
void dijkstra(int s)
{
    for(int i=0;i<=n;i++)d[i]=INF;
    d[s]=0;
    for(int i=1;i<n;i++){
        int u=0;
        for(int j=1;j<=n;j++)
        if(!vis[j]&&d[j]<d[u])
        u=j;
        vis[u]=1;
        for(auto ed:e[u]){
            int v=ed.v,w=ed.w;
            if(d[v]>d[u]+w)
            d[v]=d[u]+w;
        }

    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        e[a].push_back({b,c});
    }
    dijkstra(1);
    int t=d[n];
    if(t==INF)cout<<-1;
    else cout<<t;
    return 0;
}