链接：https://ac.nowcoder.com/acm/problem/14369 来源：牛客网
对于本文中涉及算法原理可自行百度，或者参考我的其他博客，在计算机基础分类下
题目描述简单暴力的题目要求： 给定一个有n个顶点（从1到n编号），m条边的有向图（其中某些边权可能为 负，但保证没有负环）。请你计算从1号点到其他点的最短路。
输入描述:第一行两个整数n, m。 接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出描述:共n-1行，第i行表示1号点到i+1号点的最短路。
示例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，保证从任意顶点都能到达其他所有顶点。
题目解析本题要求1到任意点的最短路，即任意两点之间的最短路径问题 注意有负权 对于这个问题我们可以使用Floyd算法或者SPFA算法 题目中说明不会存在负环 观察数据量要求，Floyd算法不适用，所以这道题是一个SPFA算法的模板题 对于SPFA是对于BFS算法的优化，加入了动态更新。
代码展示 #include <iostream> #include <cstring> #include <queue> using namespace std; const int N = 2e4+10; const int M = 2e5+10; const int inf = 0x3f3f3f3f; struct edge{ int v, w, next; edge(){} edge(int _v, int _w, int _next){ v = _v; w = _w; next = _next; } }e[M]; int head[N], size; void init(){ memset(head, -1, sizeof(head)); size = 0; } void insert(int u, int v, int w){ e[size] = edge(v, w, head[u]); head[u] = size++; } void insert2 (int u, int v, int w){ insert(u, v, w); insert(v, u, w); } int n, m; int dis[N]; bool vis[N]; void spfa(int u){ memset(vis, false, sizeof(vis)); vis[u] = true; memset(dis, inf, sizeof(dis)); dis[u] = 0; queue<int> q; q.push(u); while(!q.empty()){ u = q.front(); q.pop(); vis[u] = false; for (int j=head[u]; ~j; j=e[j].next){ int v = e[j].v; int w = e[j].w; if(dis[v] > dis[u]+w){ dis[v] = dis[u]+w; if(!vis[v]){ q.push(v); vis[v] = true; } } } } } int main(){ init(); cin >> n >> m; int a, b, c; while(m--){ cin >> a >> b >> c; insert(a, b, c); } spfa(1); for (int i=2; i<=n; i++){ cout << dis[i] << endl; } return 0; }