先这样吧，剩下的晚上再补
上午
爆蛋，并且并不想改
下午
爆蛋
T1 貌似跑一遍多源最短路再一遍暴力DFS就能过了，但O（n^3）的复杂度最大的点跑31ms属实很奇怪。
代码如下
#include
using namespace std;
int n,e,C,M,ss,tt,st[1005][1005],p[1005][1005],pv[1005][1005],nw;
int ff[1005][1005],fp[1005];//fast visit
double f[1005][1005];
queueA;
double dfs(int a,int b)//a!=b
{
/* if(a==b)
{
return f[a][b]=0.0;
}*/
if(b==0)
{
return 0;
}
// cout<<a<<" "<<b<<endl;
if(f[a][b]!=0)
{
return f[a][b];
}
if(p[p[a][b]][b]==b||p[a][b]==b)
{
f[a][b]=1.000;
return 1.000;
}
for(int i=0;i>n>>e;
cin>>C>>M;
for(int i=1;i<=e;i++)
{
scanf("%d%d",&ss,&tt);
ff[ss][fp[ss]]=tt;
ff[tt][fp[tt]]=ss;
fp[ss]++;
fp[tt]++;
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
st[i][j]=1147483647;
pv[i][j]=2147483647;
// p[i][j]=1147483647;
}
}
for(int i=0;i<=n;i++)
{
st[i][i]=0;
}
for(int i=1;i<=n;i++)
{
A.push(i);
while(!A.empty())
{
nw=A.front();
A.pop();
for(int j=0;jst[i][nw]+1)
{
A.push(ff[nw][j]);
st[i][ff[nw][j]]=st[i][nw]+1;
}
}
}
}
for(int i=1;i<=n;i++)//now
{
for(int j=1;j<=n;j++)
{
if(i!=j)
{
for(int k=0;k<fp[i];k++)
{
// cout<<"DWW"<<endl;
if(st[ff[i][k]][j]<pv[i][j])
{
pv[i][j]=st[ff[i][k]][j];
p[i][j]=ff[i][k];
// cout<<"DWWWWWWWWWWWWWWWWWWWW"<ff[i][k])
{
p[i][j]=ff[i][k];
}
}
}
}
}
/* for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<i<<" - "<<j<<" "<<p[i][j]<<endl;
}
}*/
printf("%.3lf",dfs(C,M));
}