可以使用 floyd(偷懒好算法)
但由于ACwing评测机有点慢,需要吸口氧气
把同一个公交的站点之间的距离设为 1
不同公交线路的站点设为无限大
然后跑一遍 N^3 算法输出 1到n的最短路-1 即可
为什么这是正确的?
请自己手动画图证明,既然你无法证明他是错的,那他就是对的(滑稽)
然后加个字符输入优化就可以了
参考代码
(代码来自网络)
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int Max=505;
int n,m,f[Max][Max],tot,num[Max],x;
int main()
{
scanf("%d%d",&m,&n);
memset(f,0x3f3f3f,sizeof(f));
for(int i=1;i<=m;i++)
{
tot=0;char ch='0';
do
{
if(ch=='\n')break;
scanf("%d",&x);
num[++tot]=x;
}while(scanf("%c",&ch)!=EOF);
for(int i=1;i<tot;i++)
for(int j=i+1;j<=tot;j++) f[num[i]][num[j]]=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]);
if(f[1][n]<=m+1) cout<<f[1][n]-1;
else cout<<"NO";
return 0;
}