題目分析

來源：acwing

分析：
多源匯最短路。所以我們首先想到的是floyd算法， 可是它的復雜度是$O(n^3)$，會超時。所以我們需要另外考慮。

任意一個點作為起點求出到所有點的最短距離，之后求和。 這個過程要對每個點做一遍。

樸素版dijkstra，做一遍是$O(n^2)$ ，然后對n個點做，復雜度是$O(n^3)$,太慢，不能用。

堆優化版的dijkstra，做一遍時間復雜度$O(mlogn)$，然后對n個點做，復雜度是$O(mnlogn)$,可以過！

spfa，做一遍時間復雜度$O(m)$，做一遍最壞是$O(mn)$這里沒卡 .然后對n個點做，復雜度是$O(nm)$,可以做。

具體寫法：

這里用spfa來求每個點作為起點的最短路，然后求和。

spfa需要用到queue，queue取隊頭的操作是front（）

當然也可以用堆優化的dijkstra來做，有時間再寫吧。這里是復習一下spfa。

關于spfa的模板題：
最短路[Dijkstra和堆優化的Dijkstra][Bellman-Ford和SPFA][Floyd最短路]（更新中）

ac代碼

#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> PII; const int N = 810, M = 3000;//無向邊 const int INF = 0x3f3f3f3f; int n, p, m; int id[N]; // 每個奶牛的牧場編號 int h[N],e[M],ne[M],w[M],idx; int dist[N],q[N]; bool st[N]; // spfa中的判重數組void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; }int spfa(int start){memset(dist, 0x3f, sizeof dist);dist[start] = 0;queue<int> q;q.push(start);st[start] = true;while(q.size()){int t = q.front();q.pop();st[t] = false;for(int i = h[t]; ~i; i = ne[i]){int j = e[i];if(dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if(!st[j]){q.push(j);st[j] = true;}}}}int res = 0;// 遍歷每頭牛在哪兒，然后路徑求和for(int i = 0; i < n; i ++){int j = id[i]; // if(dist[j] == INF) return INF;res += dist[j];}return res; }int main(){cin >> n >> p >> m; // 牛的個數，點數，邊數for(int i = 0; i < n ; i++) cin >> id[i]; // 讀入每頭牛在哪個點memset(h, -1, sizeof h);for(int i = 0; i < m; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b,a,c);}int res = INF;for(int i = 1; i <= p; i ++) res = min(res, spfa(i));//傳入起點cout << res << endl; }

題目來源

https://www.acwing.com/problem/content/1129/

總結

以上是生活随笔為你收集整理的算法提高课-图论-单源最短路的建图方式-AcWing 1127. 香甜的黄油：spfa最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。