[POJ1797] Heavy Transportation（最大生成树 || 最短路变形）

传送门

1.最大生成树

　　可以求出最大生成树，其中权值最小的边即为答案。

2.最短路

　　只需改变spfa里面的松弛操作就可以求出答案。

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 const int MAXN = 1005; 8 int T, n, m, cnt; 9 int head[MAXN], next[MAXN * MAXN], to[MAXN * MAXN], val[MAXN * MAXN], dis[MAXN]; 10 bool vis[MAXN]; 11 queue <int> q; 12 13 inline void add(int x, int y, int z) 14 20 21 inline void spfa(int u) 22 46 } 47 } 48 } 49 } 50 51 int main() 52 66 spfa(1); 67 printf("Scenario #%d:\n", i); 68 printf("%d\n\n", dis[n]); 69 } 70 return 0; 71 }
View Code

上一篇：[luoguP1169] [ZJOI2007]棋盘制作（单调栈）

下一篇：[luoguP2444] [POI2000]病毒（AC自动机 + dfs）

---

spfa 最短路 最小生成树