传送门:洛谷P2296 | MFOJ
作者:xzqiaochu
Solution
一道没有背景的题目……
这是一道最短路的变式题,要先要排除一些非法的点。
如上图所示,我们考虑建立反向边,从终点向起点跑一遍最短路算法(其实BFS就行)。
绿色叉叉的两个点无法被访问,说明这两个点无法通向终点。如果存在一个点指向他们,那么这个点是非法的。(即图中蓝色叉叉的点是非法的)
去除非法的点后,再跑一遍最短路算法就可以啦~
Code
//[NOIP2014]-Day2-B-寻找道路(road)
//http://www.mfstem.org/contest/19/problem/A
//author: xzqiaochu
//status: AC
//algorithm: 通过反向边删除非法的点
//time: 2019/11/12
#include <cstdio>
#include <cstring>
#include <utility>
#include <queue>
using std::priority_queue;
using std::pair;
using std::make_pair;
const int VSZ = 1e4 + 7, MSZ = 2e5 + 7;
const int INF = 0x3f3f3f3f, EPS = 100;
int n, m, s, t;
int tot, head[VSZ];
struct Edge {
int x, y, next;
} edge[MSZ];
int dis[VSZ];
bool vis[VSZ], not_use[VSZ];
inline void addEdge(int x, int y) {
edge[++tot].x = x, edge[tot].y = y;
edge[tot].next = head[x], head[x] = tot;
}
void Dijkstra(int sta, int tar) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
priority_queue< pair<int, int> > q;
dis[sta] = 0;
q.push(make_pair(0, sta));
while (!q.empty()) {
int x = q.top().second; q.pop();
if (vis[x])
continue;
vis[x] = true;
for (int i = head[x]; i; i = edge[i].next) {
int y = edge[i].y;
if (!not_use[y] && dis[x] + 1 < dis[y]) {
dis[y] = dis[x] + 1;
q.push(make_pair(-dis[y], y));
}
}
}
}
int main() {
// freopen("road.in", "r", stdin);
// freopen("road.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
addEdge(y, x); //添加反向边
}
scanf("%d%d", &s, &t);
Dijkstra(t, s);
memset(head, 0, sizeof(head)), tot = 0; //清空链式前向星,重新建图
for (int i = 1; i <= m; i++) {
if (vis[edge[i].x] == false) //反向边终点未被访问 => 边i未被访问 =>
not_use[edge[i].y] = true; //(在正向图中)边i无法通向终点 => 该边的起点是非法的
addEdge(edge[i].y, edge[i].x); //一个for循环就可以
}
Dijkstra(s, t);
if (dis[t] > INF - EPS)
printf("-1");
else
printf("%d", dis[t]);
return 0;
}