Fork me on GitHub

Codeforces238E

Codeforces238E题解

题意:

  • 有一张$n$个点,$m$条边的有向图,有$k$种巴士,每种巴士有一个起点$s_i$和终点$t_i$,每一个时刻,巴士都会等概率选择一条两点间的最短路径。
  • 询问一次从$a$到$b$最坏情况下最少需要乘坐几种巴士。
  • $n \leq 100,m \leq n \times (n-1),k \leq 100$

题解:

  • 首先我们需要知道每个巴士的路径上的必经点。
  • 然后我们可以通过用$dp[i]$表示从$i$到$b$最坏情况的最少次数。
  • 不断地尝试用$k$种巴士来更新答案,到不能更新时停止。
  • 每次更新时采用记忆化搜索。
  • 保证上车点是必经点的情况下,尝试更新。

代码:

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
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 109
using namespace std;
int f[N][N],n,m,s,t,b_num,dp[N],vis[N],Dp[N],T;
map<int,int> mp;
struct bus
{
int s,t;
int vis[N];
vector<int> q;
void st()
{
memset(vis,0,sizeof(vis));
int cnt=0;
for (int now:q) vis[now]=f[s][now]+1;
}
}b[N];
int dfs(int x,int pos)
{
if (vis[x]==T) return Dp[x];
vis[x]=T;
int ret=-1;
for (int i=1;i<=n;i++)
if (f[x][i]==1&&1+f[i][b[pos].t]==f[x][b[pos].t]) ret=max(ret,dfs(i,pos));
if (ret==-1) ret=1e9;
ret=min(ret,dp[x]);
return Dp[x]=ret;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>s>>t;
memset(f,0x3f,sizeof(f));
for (int i=1;i<=n;i++) f[i][i]=0;
for (int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
f[x][y]=1;
}
cin>>b_num;
for (int i=1;i<=b_num;i++)
cin>>b[i].s>>b[i].t;
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (f[i][k]+f[k][j]<f[i][j]) f[i][j]=f[i][k]+f[k][j];
for (int i=1;i<=b_num;i++)
{
mp.clear();
if (f[b[i].s][b[i].t]>n) continue;
for (int j=1;j<=n;j++)
if (f[b[i].s][b[i].t]==f[b[i].s][j]+f[j][b[i].t]) mp[f[b[i].s][j]]++;
for (int j=1;j<=n;j++)
if (f[b[i].s][b[i].t]==f[b[i].s][j]+f[j][b[i].t]&&mp[f[b[i].s][j]]==1) b[i].q.push_back(j);
b[i].st();
}
memset(dp,0x3f,sizeof(dp));
dp[t]=0;
int flag=1;
while (flag)
{
flag=0;
for (int i=1;i<=b_num;i++)
for (int j=1;j<=n;j++)
if (b[i].vis[j])
{
T++;
int tmp=dfs(j,i)+1;
if (tmp<dp[j])
{
flag=1;
dp[j]=tmp;
}
}
}
if (dp[s]>n) puts("-1");
else cout<<dp[s]<<endl;
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces238E

文章作者:wzf2000

发布时间:2017年12月23日 - 22:12

最后更新:2017年12月26日 - 03:12

原始链接:https://wzf2000.github.io/2017/12/23/Codeforces238E/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。