[luoguP1186] 玛丽卡（spfa）

传送门

因为要随机删除一条边，而枚举所有边肯定会超时，经过发现，先求出一遍最短路，而要删除的边肯定在最短路径上，删除其他的边对最短路没有影响。

所以可以先求出最短路，再枚举删除最短路上的每一条边再求最短路。

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 6 using namespace std; 7 8 const int MAXN = 1001; 9 int n, m, cnt, ans, qu, qv; 10 int head[MAXN], to[MAXN * MAXN], next[MAXN * MAXN], val[MAXN * MAXN], dis[MAXN], pre[MAXN]; 11 bool vis[MAXN], flag; 12 queue <int> q; 13 14 inline void add(int x, int y, int z) 15 21 22 inline void spfa(int u) 23 48 } 49 } 50 } 51 } 52 53 int main() 54 65 spfa(1); 66 flag = 1; 67 for(i = n; i != 1; i = pre[i]) 68 74 printf("%d", ans); 75 return 0; 76 }
View Code

上一篇：[luoguP3606] [USACO17JAN]Building a Tall Barn建谷仓（贪心 + 线段树）

下一篇：[HDU1576] A/B（扩展欧几里得）

---

spfa 最短路