title: ‘算法训练-最短路(BF)’date: 2020-03-06 16:17:33
tags: [蓝桥杯]
published: true
hideInList: false
feature:
isTop: false

  1. /*
  2. 试题 算法训练 最短路
  4. 资源限制
  5. 时间限制：1.0s   内存限制：256.0MB
  6. 问题描述
  7. 给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。
  8. 请你计算从1号点到其他点的最短路（顶点从1到n编号）。
  10. 输入格式
  11. 第一行两个整数n, m。
  13. 接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
  15. 输出格式
  16. 共n-1行，第i行表示1号点到i+1号点的最短路。
  17. 样例输入
  18. 3 3
  19. 1 2 -1
  20. 2 3 -1
  21. 3 1 2
  22. 样例输出
  23. -1
  24. -2
  25. 数据规模与约定
  26. 对于10%的数据，n = 2，m = 2。
  28. 对于30%的数据，n <= 5，m <= 10。
  30. 对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，
  31. -10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。
  32. */
  33. #include<cstdio>
  34. #include<vector>
  35. using namespace std;
  36. struct Node{
  37.     int v;
  38.     int dis;
  39.     Node(int _v,int _dis){
  40.         v = _v;
  41.         dis = _dis;
  42.     }
  43. };
  44. vector<Node> Adj[20001];
  45. #define maxL (1 << 30)
  46. int main(){
  47.     int n, m;
  48.     scanf("%d%d", &n, &m);
  50.     for (int i = 1; i <= m; i++){
  51.         int u, v, l;
  52.         scanf("%d%d%d", &u, &v, &l);
  53.         Node node = Node(v, l);
  54.         Adj[u].push_back(node);
  55.     }
  56.     int d[20001];
  57.     fill(d, d + 20001, maxL);
  58.     d[1] = 0;
  59.     bool update;
  60.     while (true){
  61.         update = false;
  62.         for (int i = 1; i <= n; i++){
  63.             for (int j = 0; j < Adj[i].size(); j++){
  64.                 int v = Adj[i][j].v;
  65.                 int dis = Adj[i][j].dis;
  66.                 if (d[i] + dis < d[v]){
  67.                     d[v] = d[i] + dis;
  68.                     update = true;
  69.                 }
  70.             }
  71.         }
  72.         if(!update){
  73.             break;
  74.         }
  75.     }
  77.     for (int i = 2; i <= n; i++){
  78.         printf("%d\n", d[i]);
  79.     }
  80. }