题意：给定一张无向图，每条边都有一个通过的概率 ，如果无法通过，那么就要回到起点重新出发
从起点到终点的时间固定为K，如果成功到达，又需要额外花费K的时间，问走S次的最小期望时间
思路：这道题分为两部分，第一部分是求spfa，第二部分是通过得出的最大的概率的那条路算出答案；怎么算呢，通过最短路求出后，设期望值为E，成功概率为p，如果成功，期望值为p*2k，如果不成功，期望值为(1-p)*(E+2k)因此E=p*2k+(1-p)*(E+2k),化简为E=2k/p最后再乘上s
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<queue>
using namespace std;
const int maxn=1e4+;
const int inf=0x3f3f3f3f;
int head[maxn],num=-;
int s,t;
double dis[maxn];int vis[maxn];
struct node
{
int v,next;
double w;
}G[maxn];
void build(int u,int v,double w)
{
G[++num].v=v;G[num].w=w;G[num].next=head[u];head[u]=num;
G[++num].v=u;G[num].w=w;G[num].next=head[v];head[v]=num;
}
void init()
{
memset(head,-,sizeof(head));
num=-;
}
void SPFA()
{
memset(dis,,sizeof(dis));
dis[]=;
queue<int>q;
q.push();
vis[]=;
while(!q.empty()){
// printf("11111111111111111111111111\n");
int u=q.front();
q.pop();
vis[u]=;
for(int i=head[u];i!=-;i=G[i].next){
int v=G[i].v;double w=G[i].w;
if(dis[v]<dis[u]*w){
dis[v]=dis[u]*w;
if(!vis[v]){
q.push(v);
vis[v]=;
}
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
int cnt=;
while(T--){
init();
int n,m,s,k;
scanf("%d%d%d%d",&n,&m,&s,&k);
for(int i=;i<=m;i++){
int u,v;double w;
scanf("%d%d%lf",&u,&v,&w);
w=w/;
build(u,v,w);
}
SPFA();
double ans=dis[n-];
double tmp=1.0/ans;
tmp=(double)(tmp**k*s);
printf("Case %d: %lf\n",++cnt,tmp);
}
return ;
}