Solution
通过最短路和 \(n\leq 100\) 得知我们可以拿 \(floyd\) 预处理全源最短路。然后因为要换车,所以我们可以考虑dp,设 \(dp_i\) 为 \(i\) 到终点 \(b\) 的最坏换车次数,但是从起点开始可能会有后效性,所以从终点开始,即 \(dp_b\) 为 \(0\) 。
对于路线 \(k\) ,不一定只有一条最短路,所以我们考虑 \(k\) 必然经过的点。但是模拟一下发现只考虑必经点是不行的,某条最短路上的非必经点可能是别的路线的必经点。所以选择拿 \(dfs\) 来搜索情况,并及时更新。
注意:可能会出现环,所以要判断。
时间复杂度 \(O(n^4)\) 。还有一些注意点写在代码里了。
代码
#include<bits/stdc++.h>
using namespace std;
int vis[105],T,num[105],dp[105],f[105][105],n,m,K,DP[105],s[105],t[105];
bool b[105][105];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
int dfs(int u,int k){
//u是当前点,k是路线,计算u点只坐这条公交路线到达终点最坏情况的换乘次数
if(vis[u]==T) return DP[u];
int tmp=-1;vis[u]=T;
for(int v=1;v<=n;v++)
if(f[u][v]==1&f[u][t[k]]==f[v][t[k]]+1)
//判断u和v是否有边 u->v是k这条路线最短路径上的边
tmp=max(tmp,dfs(v,k));
if(tmp==-1) tmp=1e9;
if(tmp>dp[u]) tmp=dp[u];
//dp[u]表示从u到终点的最小换乘次数(u为必经点)
return DP[u]=tmp;//因为可能有环所以要记一个DP
}
int main(){
scanf("%d%d%d%d",&n,&m,&s[0],&t[0]);
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++) f[i][j]=f[j][i]=1e9;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
f[u][v]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
scanf("%d",&K);
for(int i=1;i<=K;i++){
scanf("%d%d",&s[i],&t[i]);
if(f[s[i]][t[i]]==1e9) continue;
for(int j=1;j<=n;j++)
if(f[s[i]][j]+f[j][t[i]]==f[s[i]][t[i]])
num[f[s[i]][j]]++;
for(int j=1;j<=n;j++)
if(f[s[i]][j]+f[j][t[i]]==f[s[i]][t[i]]){
if(num[f[s[i]][j]]==1) b[i][j]=1;//i路线的最短路径上的某个点可能会经过多条边,所以要寻找必经点
num[f[s[i]][j]]=0;
}
}
for(int i=1;i<=n;i++) dp[i]=DP[i]=1e9;
dp[t[0]]=0;
bool flag=1;
while(flag){
flag=0;
for(int i=1;i<=K;i++)
for(int j=1;j<=n;j++)
if(b[i][j]){
T++;//只是dfs来判环用的
int tmp=dfs(j,i)+1;//在此算上了一次车,所以+1
if(tmp<dp[j]){
flag=1;//如果更新了答案,那需要再枚举一遍必经点
dp[j]=tmp;//dp值只在这里更新,有意义的dp值为必经点
}
}
}
if(dp[s[0]]==1e9) dp[s[0]]=-1;
printf("%d\n",dp[s[0]]);
return 0;
}