【藍橋杯】ALGO-5 最短路

• 2019 年 11 月 13 日
• 筆記

版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。

本文鏈接：https://blog.csdn.net/weixin_42449444/article/details/102962166

題目描述：

給定一個n個頂點，m條邊的有向圖（其中某些邊權可能為負，但保證沒有負環）。請你計算從1號點到其他點的最短路（頂點從1到n編號）。

輸入描述：

第一行兩個整數n, m。接下來的m行，每行有三個整數u, v, l，表示u到v有一條長度為l的邊。（1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000），保證從任意頂點都能到達其他所有頂點。

輸出描述：

輸出共n-1行，第i行表示1號點到i+1號點的最短路。

輸入樣例：

3 3  1 2 -1  2 3 -1  3 1 2

輸出樣例：

-1  -2

解題思路：

Dijkstra演算法無法判斷含負權邊的圖的最短路，Floyd演算法時間複雜度為O(n³)，故均不考慮。這裡用Bellman-Ford演算法，它能在存在負權邊的情況下解決單源點最短路徑問題。

AC程式碼：

#include <bits/stdc++.h>  using namespace std;  #define Up(i,a,b) for(int i = a; i <= b; i++)  #define ms(a,x) memset(a,x,sizeof(a))  const int INF = 0x3f3f3f3f;  const int maxn = 200001;    int u[maxn],v[maxn],w[maxn];  int d[maxn];    //記錄起點1到各點的最短距離    int main()  {      ios::sync_with_stdio(false);      cin.tie(0),cout.tie(0);      ms(d,INF);  //初始化圖的資訊      d[1] = 0;   //1到自身的距離為0      int n,m;    //頂點數n,邊數m      cin >> n >> m;      Up(i,1,m)      {          cin >> u[i] >> v[i] >> w[i];      }      Up(i,1,n-1)      {          bool flag = false;          Up(j,1,m)          {              if(d[v[j]] > d[u[j]]+w[j])              {                  d[v[j]] = d[u[j]]+w[j];   //更新最短路                  flag = true;              }          }          if(!flag) break;   //若不再更新最短路,提前退出循環      }      Up(i,2,n)      {          cout << d[i] << endl;      }      return 0;  }