链接
http://codeforces.com/contest/1321/problem/D
题意
连通有向图
有一条已经计划好的从s到t的路径，你按照计划好的路径驾驶
在起点时，导航系统给出一条从起点到达终点的最短路径
计划路径可能和导航给出的最短路径不同
所以每当你按照出发前计划的路径移动一个点时，导航可能会重置最短路径
当最短路径不唯一时，导航会随机给出一条
问导航最少和最多重置最短路径几次
思路
最短路
先倒着建图，通过bfs算出每个点到终点的距离 $d$
当从 $u$ 移动到 $v$ 时：
当 $d[v]>d[u]-1$ 时，肯定会重置
当 $d[v]=d[u]-1$ 时，若存在一个点 $w(w \neq v)$ 使 $d[w]+1=d[u]$，则可能会重置
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m,k;
int u[N],v[N];
int path[N];
int cnt,to[N],nxt[N],head[N];
int d[N];
void addedge(int u,int v) {
cnt++;
to[cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void bfs() {
queue<int>q;
q.push(path[k]);
d[path[k]]=1;
while(q.size()) {
auto u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];
if(d[v]) continue;
d[v]=d[u]+1;
q.push(v);
}
}
}
void solve() {
cnt=0;
memset(head,0,sizeof head);
for(int i=1;i<=m;i++) addedge(u[i],v[i]);
int mn=0,mx=0;
for(int i=1;i<k;i++) {
if(d[path[i+1]]>=d[path[i]]) mx++,mn++;
else for(int j=head[path[i]];j;j=nxt[j]) {
int x=to[j];
if(d[x]==d[path[i]]-1&&x!=path[i+1]){mx++;break;}
}
}
cout<<mn<<" "<<mx<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++) {
cin>>u[i]>>v[i];
addedge(v[i],u[i]);
}
cin>>k;
for(int i=1;i<=k;i++) cin>>path[i];
bfs();
solve();
return 0;
}
|