给定一个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 <iostream> #include<vector> #include<string.h> #include<cstdio> using namespace std; int a[20004][20004]; int dist[20002]; int visited[20002]; int n,m; int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int u,v,l; cin>>u>>v>>l; if(a[u][v]){ a[u][v]=min(l,a[u][v]); a[v][u]=min(l,a[v][u]); } else{ a[u][v]=l; a[v][u]=l; } } memset(visited,0,sizeof(visited)); visited[1]=1; for(int i=1;i<=n;i++) { dist[i]=a[1][i]; } int index; for(int i=1;i<n;i++) { int minncost=100003; for(int j=1;j<=n;j++) { if(!visited[j]&&dist[j]<minncost) { minncost=dist[j]; index=j; } } visited[index]=1; for(int j=1;j<=n;j++) { if(!visited[j]&&dist[index]+a[index][j]<dist[j]) { dist[j]=dist[index]+a[index][j]; } } } for(int i=2;i<=n;i++) { cout<<dist[i]<<endl; } return 0; } 超时，用的单源最短路径算法，这题要用spfa，即堆优化的
#include <iostream> #include<vector> #include<string.h> #include<cstdio> #include<queue> using namespace std; typedef struct mm { int t,w; }node; vector < node > map[20005]; int dist[20005]; int visited[20005]; void spfa() { queue<int> q; q.push(1); dist[1]=0; visited[1]=1; while(!q.empty()) { int t=q.front(); q.pop(); visited[t]=0; int len=map[t].size(); int a; for(int i=0;i<len;i++) { a=map[t][i].t; if(dist[a]>map[t][i].w+dist[t]) { dist[a]=map[t][i].w+dist[t]; if(!visited[a]) { visited[a]=1; q.push(a); } } } } } int main() { int n,m; cin>>n>>m; node now; for(int i=1;i<=n;i++) dist[i]=99999999; for(int i=1;i<=m;i++) { int u,v,l; cin>>u>>v>>l; now.t=v; now.w=l; map[u].push_back(now); } spfa(); for(int i=2;i<=n;i++) { cout<<dist[i]<<endl; } return 0; } 用到stl,这里vector<node>map[],这里一定要定义成map
