编辑代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0xffff

void scan(vector<vector<int>> &node,int m,int n)
{
    int a, b, len;
    for(int i=0;i<n;i++)    node[i][i]=0;
    while (m--){
        scanf("%d %d %d",&a,&b,&len);
        if (node[a-1][b-1]!=INF and node[a-1][b-1]<=len)    continue ;
        if (a!=b){
            node[a-1][b-1] = len; 
        }
    }

}

void update(int ori,vector<int> &dis,vector<int> &side )
{

    for(int i=0;i<dis.size();i++)
        dis[i]=min(side[i]+dis[ori],dis[i]);
}

int query(auto &dis,auto &visit)
{
        int res=INF;int pos=0;
        for(int i=0;i<dis.size();i++){
            if (visit[i] && dis[i]<res){
                pos=i;res=dis[i];
            }
        }
        return pos;
}

void dijkstra(auto &node,vector<int> &dis,int ori)
{
    vector<int> visit(dis.size(),1);

    for(int _=0;_<dis.size();_++)
    {
        update(ori,dis,node[ori]);
        visit[ori]=0;
        ori=query(dis,visit);
    }

    for(auto i:dis){
        if (i!=INF)
        cout<<i<<' ';
        else cout<<"2147483647" <<' ';
    }
       
    return ;
}

int main()
{
    int n,m,ori;
    cin>>n>>m>>ori;
    vector<vector<int>> node(n, vector<int>(n, INF));

    scan(node,m,n);
    vector<int> dis=node[ori-1];
    dijkstra(node,dis,ori-1);
    return 0;
}