题解 | #最短路#

前向星图+spfa

#include<bits/stdc++.h>
using namespace std;
int n,m;
int head[200005],dist[200005],flag[200005];
int cnt=0;
queue<int>q;
struct Edge{
    int v,next,dis;
}edge[200005];

void addedge(int u,int v,int dis){
    cnt++;
    edge[cnt].v=v;
    edge[cnt].dis=dis;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void spfa(int t){
    memset(dist,127,sizeof(dist));
    memset(flag,0,sizeof(flag));
    dist[t]=0;
    q.push(t);
    flag[t]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        flag[x]=0;
        for(int i=head[x];i;i=edge[i].next){
            if(dist[edge[i].v]>dist[x]+edge[i].dis){
                dist[edge[i].v]=dist[x]+edge[i].dis;
                if(!flag[edge[i].v]){
                    q.push(edge[i].v);
                    flag[edge[i].v]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(i!=t){
            cout<<dist[i]<<endl;
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,dis;
        cin>>u>>v>>dis;
        addedge(u,v,dis);
    }
    spfa(1);
}