「NOIP2014」寻找道路

发表于 | 分类于

题目链接

在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：

  • 路径上的所有点的出边所指向的点都直接或间接与终点连通。 在满足条件1的情况下使路径最短。
  • 注意：图 G 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

输入输出格式
输入格式：

第一行有两个用一个空格隔开的整数 n 和 m，表示图有 n 个点和 m 条边。

接下来的 m 行每行 2 个整数 x,y，之间用一个空格隔开，表示有一条边从点 x 指向点y。

最后一行有两个用一个空格隔开的整数 s,t，表示起点为 s，终点为 t。

输出格式：

输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出−1。

输入输出样例
输入样例#1：

3 2

1 2

2 1

1 3

输出样例#1：

-1

输入样例#2：

6 6

1 2

1 3

2 6

2 5

4 5

3 4

1 5

输出样例#2：

3

说明
解释1：

如上图所示，箭头表示有向道路，圆点表示城市。起点11与终点33不连通，所以满足题目描述的路径不存在，故输出−1 。

解释2：

如上图所示，满足条件的路径为1- >3- >4- >5。注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。

当我读完这道题的时候，noip竟然会考这么裸的最短*？ 对，这当然是我的错觉。看到样例解释2的时候我就明白了这道题才没有那么naive；

但是我头铁嘛对不对，先写个dijkstra试一试叭；

嗯，第一个样例没问题，但是第二个样例，我得到了答案：2——这显然是没有考虑条件2；

我们这样想，和终点不 直接或间接 连接， 那么我们如果建一个反图，反跑（以终点为起点）一遍dijkstra，如果某个点的最短距离为INF，显然这个点和终点（正常图）是不连接的；

我们把和终点（正常图）不连接的点找到了，下一步，我们就去找图（正常图）中出边与这些点直接相连的点，打上标记，表明这些点是不可出现在题目中要求的最短路径中的；node[N_MAX] 、vis[N_MAX]；

把去点操作完成之后， 忽然发现，既然只要输出最短路径长度即可，那么反图和正常图跑出来的结果就是一样的！okay,直接在之前建好的反图上面再跑一边dijkstra，问题解决了！上代码！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <cstdio>
#include <cctype>
#include <queue>
#include <vector>
 
using namespace std;
 
#define DEBUG(x) std::cerr << #x << " = " << x << std::endl
//DEBUG时用的操作
 
inline int read() {
	char ch = getchar(); int res = 0; int flag = 1;
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') flag = -1;
	for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + ch - '0';
	return (res * flag);
}//快读
 
const int INF = 0x7fffffff;
const int N_MAX = 10000 + 7;
const int M_MAX = 200000 + 7;
int n, m, num, head[N_MAX], dist[N_MAX], ans, tot, start, endd;
bool vis[N_MAX];//判断某个点是否符合条件2；
 
struct Node{
	vector<int>vec;
}node[N_MAX];//储存和终点不相连的点的“父亲”；
 
struct Edge{
	int to, w, next, from;
}edge[M_MAX];
 
inline void add_edge(int from, int to, int w) {
	edge[++num].to = to;
	edge[num].from = from;
	edge[num].w = w;
	edge[num].next = head[from];
	head[from] = num;
}
 
struct Dist{
	int x, dist;
	Dist(int x = 0, int dist = INF) : x(x), dist(dist) {}
	bool operator()(Dist l, Dist r) {
		return l.dist > r.dist;
	}
};
 
priority_queue <Dist, vector<Dist>, Dist> que;
 
void dijkstra() {
	for(int i = 1; i <= n; i++) {
		dist[i] = INF;
	}
	dist[start] = 0;
	que.push(Dist(start, 0));
	while(!que.empty()) {
		Dist tmp = que.top();
		que.pop();
		if(vis[tmp.x]) continue;//如何这个点非法，即不满足条件2；
		if(dist[tmp.x] != tmp.dist) continue;
		for(int j = head[tmp.x]; j; j = edge[j].next) {
			if(dist[edge[j].to] > dist[edge[j].from] + edge[j].w) {
				dist[edge[j].to] = dist[edge[j].from] + edge[j].w;
				que.push(Dist(edge[j].to, dist[edge[j].to]));
			}
		}
	}
}
 
int main() {
	n = read(); m = read();
	for(int i = 1; i <= m; i++) {
		int x = read(), y = read();
		add_edge(y, x, 1);//建反图；
		node[y].vec.push_back(x);//存“父亲”；
	}
	endd = read(); start = read();//倒跑最短路；
	dijkstra();
	for(int i = 1; i <= n; i++) {
		if(dist[i] == INF) {
			vis[i] = 1;
			while(node[i].vec.size()) {
				vis[node[i].vec.back()] = 1;
				node[i].vec.pop_back();
			}
		}
	}//判断不合法的点集；
	dijkstra();
	int t = dist[endd];
	if(t == INF) {
		printf("-1\n");
		return 0;
	}
	printf("%d\n", t);
	return 0;
}