最短路-JZTXT

无向图

Dijkstra（只能解决正权边，单源）

它的逻辑可以理解为走当前最近可到达的且无法确定它是不是最短路的一个点，找它的最短路

点击查看代码

void solve(){
    int n,m,s;
    cin>>n>>m>>s;
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        d[a][b]=c;
    }
    dis[s]=0;
    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(vis[j]==0&&(dis[t]>dis[j]||t==-1)){
                t=j;
            }
        }
        vis[t]=1;
        for(int j=1;j<=n;j++){
            dis[j]=min(dis[j],dis[t]+d[t][j]);
        }
    }

    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
}