1 #include<iostream> 2 #include<queue> 3 #include<string.h> 4 using namespace std; 5 const int INF =100000000; 6 const int MAXN =1000; 7 const int MAXM =100000; 8 int m,n; 9 int first[MAXN],d[MAXN];10 int u[MAXM],v[MAXM],w[MAXM],next[MAXM];11 typedef pair<int ,int >pii;//STL中的pair便是专门把两个类型捆绑在一起。便于关联数据的输出与提取12 priority_queue<pii ,vector<pii>,greater<pii> > q;//创建优先队列，这是自己定义的优先队列排序函13 int main()14 {15    cin>>m>>n;16    for(int e=0;e<m;e++)17    {18         cin>>u[e]>>v[e]>>w[e];19         next[e]=first[u[e]];//这里是把第e条边的起点所对应的第一条边的值赋给e的下一条边20         first[u[e]]=e; //并把第e条边的起点的第一条边设置为e 21    }22    bool done[MAXN];23    for(int i=0;i<n;i++)24    d[i]=(i==0?0:INF);25    memset(done,0,sizeof(memset));26    q.push(make_pair(d[0],0));//将第一条数据压入优先队列27    while(!q.empty())28    {29        pii u=q.top();30        q.pop();31        int x =u.second;//获得节点号,u.first是d[i]32        if(done[x]) continue;33        done[x]=1;34        for(e=first[x];e!=-1;e=next[e])35        {36            if(d[v[e]]>d[x]]+w[e])37            d[v[e]]=d[x]]+w[e];38            q.push(make_pair(d[v[e]],v[e])); //如果未被访问，则压入优先队列  39        }40        41    }42    for(int i=0;i<MAXN;i++)43    cout<<d[i]<<endl;44    return 0;45 }