分層圖最短路系列題目

分層圖最短路的題目有一個非常容易看得出的把戲：讓k條邊免費。

對于能讓\(k\)條邊免費的數據，我們開\(k+1\)層圖。每一層圖內部正常連點，不同的是前一層的圖的起點連一條權值為0的邊到下一層的終點，等價于這條邊免費了。

當然，這么建圖的話這個圖是挺大的。所以跑最短路的效率就特別重要！

還有最重要的一句話：

\(\huge{SPFA她死了！}\)

絕對不要用SPFA，除非題目真的有負權邊。

建圖什么的應該難不倒你，做過網絡流的都差不多知道怎么處理下標的關系了。

在實現的過程中要注意：層數一定要注意是\(k+1\)層，不要數組開小了RE了啊！

代碼：

#include<cstdio> #include<cstring> #include<queue> const int maxn = 10005, maxk = 11; struct Edges {int next, to, weight; } e[3000005]; int head[maxn * maxk], tot; int dist[maxn * maxk]; int n, m, k, s, t; struct HeapNodes {int d, u;bool operator < (const HeapNodes &rhs) const{return d > rhs.d;} }; void link(int u, int v, int w) {e[++tot] = (Edges){head[u], v, w};head[u] = tot; } int dijkstra(int ss, int tt) {memset(dist, 0x3f, sizeof dist);std::priority_queue<HeapNodes> heap;dist[ss] = 0;heap.push((HeapNodes){dist[ss], ss});while(!heap.empty()){HeapNodes x = heap.top(); heap.pop();int d = x.d, u = x.u;if(d != dist[u]) continue;for(int i = head[u]; i; i = e[i].next){int v = e[i].to;if(dist[u] + e[i].weight < dist[v]){dist[v] = dist[u] + e[i].weight;heap.push((HeapNodes){dist[v], v});}}}return dist[tt]; } int main() {scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);for(int i = 1; i <= m; i++){int x, y, z; scanf("%d%d%d", &x, &y, &z);link(x, y, z); link(y, x, z);// 我總共會有k+1層for(int j = 1; j <= k; j++)// 第j層向j+1層連邊{// 向j + 1層連邊link(x + j * n, y + j * n, z);link(y + j * n, x + j * n, z);link(x + (j - 1) * n, y + j * n, 0);link(y + (j - 1) * n, x + j * n, 0);}}printf("%d\n", dijkstra(s, t + k * n));return 0; }

轉載于:https://www.cnblogs.com/Garen-Wang/p/9886114.html

總結

以上是生活随笔為你收集整理的P4568 [JLOI2011]飞行路线 P2939 [USACO09FEB]改造路Revamping Trails的全部內容，希望文章能夠幫你解決所遇到的問題。

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