问题描述
Urpal lives in a big city. He has planned to meet his lover tonight.
The city has n junctions numbered from 1 to n. The junctions are connected by mdirected streets, all the roads have equal length. Urpal lives in junction a and the date is planned in a restaurant in junction b. He wants to use public transportation to get to junction b. There are k bus transportation companies. At the beginning of every second, a bus from the i-th company chooses a random shortest path between junction si and junction ti and passes through it. There might be no path from si to ti. In that case no bus will leave from si to ti. If a bus passes through a junction where Urpal stands, he can get on the bus. He can also get off the bus at any junction along the path.
Now Urpal wants to know if it's possible to go to the date using public transportation in a finite amount of time (the time of travel is the sum of length of the traveled roads) and what is the minimum number of buses he should take in the worst case.
At any moment Urpal knows only his own position and the place where the date will be. When he gets on the bus he knows only the index of the company of this bus. Of course Urpal knows the city map and the the pairs (si, ti) for each company.
Note that Urpal doesn't know buses velocity.
题目大意：给定一个 n 个点 m 条边的有向图，现在要从 a 点去到 b 点，一共有 k 条公交路线，分别从 s i 开往 t i . 每个时刻都会有一辆公交从 s i 出发并随机选择一条到t i 的最短路开过。若某个时刻有公交经过你当前所在节点则你可以上车，并在之后任意点下车。请问最坏情况下你最少要上几辆车。
输入格式
The first line of the input contains four integers n, m, a, b (2 ≤ n ≤ 100; 0 ≤ m ≤ n·(n - 1); 1 ≤ a, b ≤ n; a ≠ b).
The next m lines contain two integers each ui and vi (1 ≤ ui, vi ≤ n; ui ≠ vi)describing a directed road from junction ui to junction vi. All roads in the input will be distinct.
The next line contains an integer k (0 ≤ k ≤ 100). There will be k lines after this, each containing two integers si and ti (1 ≤ si, ti ≤ n; si ≠ ti) saying there is a bus route starting at si and ending at ti. Please note that there might be no path from si to ti, this case is described in the problem statement.
输出格式
In the only line of output print the minimum number of buses Urpal should get on on his way in the worst case. If it's not possible to reach the destination in the worst case print -1.
样例输入
#1
7 8 1 7
1 2
1 3
2 4
3 4
4 6
4 5
6 7
5 7
3
2 7
1 4
5 7
#2
4 4 1 2
1 2
1 3
2 4
3 4
1
1 4
样例输出
#1
2
#2
-1
题解
最坏的情况的意思是，除非公交必须经过你当前所在节点，否则你一定无法在此点上这辆公交。
那么就要求出每辆公交的必经点，然后记忆化搜索，f[i]表示从i到b最少换乘几次公交，不断用k条公交线路更新，直到不能更新为止。
具体看注释吧。
#include <cstdio> int n,m,a,b,Q,cnt; int s[105],t[105],dis[105][105],num[105],f[105],g[105],used[105]; bool mut[105][105]; int max(int x,int y) { return x>y?x:y; } int dfs(int x,int y) //从x到t[y]的换乘次数 { int i,j,sum=-1; if (used[x]==cnt) // 点x绕了一圈又回来了 return g[x]; // 防止陷入死循环 used[x]=cnt; for (i=1;i<=n;i++) if (dis[x][i]==1 ) //如果x到i有路 if (dis[x][t[y]]==dis[i][t[y]]+1) // 如果x经过i到达t[y] sum=max(sum,dfs(i,y)); //下面Floyd已经算出最短路，点i和点y固定，走的一定是最短路，但是要求最坏情况，所以换乘次数最多 if (sum==-1) sum=1e9; if (sum>f[x]) sum=f[x]; return g[x]=sum; } int main() { int i,j,k,x,y; scanf("%d%d%d%d",&n,&m,&a,&b); for (i=1;i<n;i++) for (j=i+1;j<=n;j++) dis[i][j]=dis[j][i]=1e9; for (i=1;i<=m;i++) scanf("%d%d",&x,&y), dis[x][y]=1; scanf("%d",&Q); for (i=1;i<=Q;i++) scanf("%d%d",&s[i],&t[i]); //Floyd for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; for (k=1;k<=Q;k++) if(dis[s[k]][t[k]]<1e9) //如果s[k]和t[k]之间有路 { for (i=1;i<=n;i++) if (dis[s[k]][i]+dis[i][t[k]]==dis[s[k]][t[k]]) //点i在s[k]到t[k]的最短路上 num[dis[s[k]][i]]++; //记录长度和从s[k]到i的长度一样的路径数 for (i=1;i<=n;i++) if (dis[s[k]][i]+dis[i][t[k]]==dis[s[k]][t[k]]) { if (num[dis[s[k]][i]]==1) //如果长度和从s[k]到i的长度一样的路径只有一条，说明从s[k]到i只有一条路径，那么i是s[k]到t[k]的必经点 mut[k][i]=1; //标记，在第k条公交线路中i是必经点 num[dis[s[k]][i]]=0; //清空，防止干扰下一条公交线路的计算 } } bool can=1; for (i=1;i<=n;i++) f[i]=g[i]=1e9; f[b]=0; while (can) { can=0; for (i=1;i<=Q;i++) for (j=1;j<=n;j++) if (mut[i][j]) //如果在第i条公交线路中点j是必经点 { cnt++; //时间戳 x=dfs(j,i)+1; //从s[i]到i需要乘一次公交 if (x<f[j]) can=1,f[j]=x; } } printf("%d",f[a]!=1e9?f[a]:-1); return 0; }