NOIP2014D2T2寻找道路（Spfa）

洛谷传送门

这道题可以把边都反着存一遍，从终点开始深搜，然后把到不了的点 和它们所指向的点都去掉。

最后在剩余的点里跑一遍spfa就可以了。

——代码

#include <cstdio> #include <cstring> #include <queue> const int maxn = 100001; int n, m, s, t, cnt1, cnt2; int dis[maxn]; int next1[4 * maxn], to1[4 * maxn], head1[4 * maxn], next2[4 * maxn], to2[4 * maxn], head2[4 * maxn]; bool vis[maxn], b[maxn], f[maxn], flag; inline void add1(int x, int y) inline void add2(int x, int y) inline void dfs(int u) } inline void spfa(int u) } } } int main() scanf("%d %d", &s, &t); dfs(t); if(!flag) for(i = 1; i <= n; i++) if(!vis[i]) spfa(s); printf("%d", dis[t]); return 0; }
View Code

上一篇：【转】二分图的一大坨定理

下一篇：树状数组 &amp;&amp; 线段树

---

最短路