传送门
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
上一篇：[HDU3065]病毒持续侵袭中（AC自动机）
下一篇：树的重心
最小生成树 最短路 spfa
