给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
输入格式第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出格式 共n-1行，第i行表示1号点到i+1号点的最短路。 样例输入 3 3 1 2 -1 2 3 -1 3 1 2 样例输出 -1 -2 数据规模与约定对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。
#include<cstdio> #include<iostream> #include<queue> #include<cstring> using namespace std; typedef pair<int,int> pii; const int m1=20000+10,m2=200000+10; int first[m1],dis[m1],n,m,v[m2],w[m2],next[m2]; void dijkstra(){ pii t; int d,x; priority_queue<pii,vector<pii>,greater<pii> > q; memset(dis,0x3f3f3f3f,sizeof(dis)); dis[1]=0; q.push(make_pair(0,1)); while(!q.empty()){ t=q.top(); q.pop(); d=t.first; x=t.second; if(dis[x]!=d) continue; for(int i=first[x];i!=-1;i=next[i]) if(dis[v[i]]>dis[x]+w[i]){ dis[v[i]]=dis[x]+w[i]; q.push(make_pair(dis[v[i]],v[i])); } } } int main(){ int a,b,c; scanf("%d%d",&n,&m); memset(first,-1,sizeof(first)); for(int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); v[i]=b; w[i]=c; next[i]=first[a]; first[a]=i; } dijkstra(); for(int i=2;i<=n;i++) printf("%d\n",dis[i]); return 0; } #include<cstdio> #include<iostream> #include<queue> #include<cstring> using namespace std; typedef pair<int,int> pii; const int m1=20000+10,m2=200000+10; int first[m1],dis[m1],n,m,v[m2],w[m2],next[m2]; bool vis[m1]; void dijkstra(){ pii t; int d,x; priority_queue<pii,vector<pii>,greater<pii> > q; memset(dis,0x3f3f3f3f,sizeof(dis)); dis[1]=0; q.push(make_pair(0,1)); while(!q.empty()){ t=q.top(); q.pop(); d=t.first; x=t.second; if(vis[x]) continue; vis[x]=true; for(int i=first[x];i!=-1;i=next[i]) if(dis[v[i]]>dis[x]+w[i]){ dis[v[i]]=dis[x]+w[i]; q.push(make_pair(dis[v[i]],v[i])); } } } int main(){ int a,b,c; scanf("%d%d",&n,&m); memset(first,-1,sizeof(first)); for(int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); v[i]=b; w[i]=c; next[i]=first[a]; first[a]=i; } dijkstra(); for(int i=2;i<=n;i++) printf("%d\n",dis[i]); return 0; }
