官方题解 | 嘉豪舞团

#include<bits/stdc++.h>
using namespace std;
long long n=1000,m,a,s,e[1005][1005],dis[1005],vis[1005];
int main(){
    cin>>m>>a>>s;
    for(long long i=1;i<=m;i++){
        long long u,v,w;
        cin>>u>>v>>w;
        if(e[u][v]==0){
            e[u][v]=1e9;
        }
        if(e[v][u]==0){
            e[v][u]=1e9;
        }
        e[u][v]=min(e[u][v],w);
        e[v][u]=min(e[v][u],w);
    }
    for(long long i=0;i<=n;i++){
        dis[i]=1e9;
    }
    dis[s]=0;
    for(long long i=1;i<=n;i++){
        long long u=0;
        for(long long j=1;j<=n;j++){
            if(!vis[j]&&dis[j]<dis[u]){
                u=j;
            }
        }
        vis[u]=1;
        for(long long j=1;j<=n;j++){
            if(e[u][j]){
                long long v=j,w=e[u][j];
                if(dis[v]>dis[u]+w){
                    dis[v]=dis[u]+w;
                }
            }
        }
    }
        if(dis[a]!=1e9){
            cout<<dis[a]<<endl;
        }
        else{
            cout<<-1<<endl;
        }
    return 0;
}