算法训练 最短路 时间限制：1.0s 内存限制：256.0MB 提交此题 锦囊1 锦囊2 问题描述 给定一个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，保证从任意顶点都能到达其他所有顶点。
注意题目给的是有带负权值的点，所以可以直接想到spfa算法来处理，由于点与点是有向图，所以建立邻接表，这里直接用vector容器来建 还要注意的是初始化需要给个大数 0x3f3f3f
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <queue> #include <vector> #define INF 0x3f3f3f using namespace std; #define N 20000+10 int map[N]; int vist[N]; int d[N]; int num[N]; int n,m; typedef struct { int v,w; }node; vector<node> Map[N]; int spfa(int s) { for(int i=0;i<n;i++) { num[i]=0; d[i]=INF; vist[i]=0; } d[s]=0; vist[s]=1; queue<int>Q; Q.push(s); num[s]++; while(!Q.empty()) { int t=Q.front(); Q.pop(); vist[t]=0; for(int i=0;i<Map[t].size();i++)///枚举和t相连的点，找最短的那个点加入队列 { int vl=Map[t][i].v; int wl=Map[t][i].w; if(d[vl]>d[t]+wl) { d[vl]=d[t]+wl; if(vist[vl]==0) { Q.push(vl); vist[vl]=1; num[vl]++; if(num[vl]>=n) return 0; } } } } return 1; } int main() { int u,v,w; scanf("%d%d",&n,&m); //memset(vist,0,sizeof(vist)); //memset(map,INF,sizeof(map)); for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); u--,v--; node e; e.v=v; e.w=w; Map[u].push_back(e); } spfa(0); for(int i=1;i<n;i++) printf("%d\n",d[i]); return 0; }