lightoj 1321 Sending Packets

题目链接：lightoj 1321

题意：从0到n-1需要传输s个包，传输的时候每条边安全到达的概率为pi，每次传输的时间为2K，如果在传输时候没有安全到达，则要重新传送，求最小的传送时间

这个题，跟概率相关的地方在于推公式

首先，s个包和传输时间2K都是可以放在最后处理的，因为都是独立的，满足加法原理，最后乘进去答案里面就好了

那么，来分析每个边和点传输成功的概率

传输成功的期望时间=传输一次成功的概率*传输一次成功的时间+传输两次成功的概率*传输两次成功的时间+……

即T=p*2K+p（1-p）*4K+p（1-p）（1-p）*6K……

即T=2pK【1+2（1-p）+3（1-p）（1-p）……】

根据高中数学知识所学，出现等差*等比的时候，需要乘以等比的值，然后两式相减，裂项来消去：

（1-p）T=2pK【（1-p）+2（1-p）（1-p）+3（1-p）（1-p）（1-p）+……】

消去后解得：T=2K/p

那么根据事件的独立性，概率越大，花的时间越小

所以把每条边所需时间算出来，找到一条从起点0到终点n-1的概率最大的路径（相乘），可以得到最小时间

代码如下：

int t,n,m,s,k;
bool vis[maxn];
double mp[maxn][maxn];

void floyd(){
	for(int i=0;i<n;i++)
		mp[i][i]=1.0;
	for(int k=0;k<n;k++)
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				mp[i][j]=mp[j][i]=max(mp[i][j],mp[k][i]*mp[k][j]);
}

int main(){
	//input;
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%d%d%d%d",&n,&m,&s,&k);
		for(int i=0;i<n;i++) dp[i]=1e14;
		memset(mp,0,sizeof(mp));
		memset(vis,0,sizeof(vis));
		int u,v,w;
		while(m--){
			scanf("%d%d%d",&u,&v,&w);
			mp[u][v]=mp[v][u]=w/100.0;
		}
		floyd();
		printf("Case %d: %.6lf\n",Case,1.0/mp[0][n-1]*2*k*s);
	}
	return 0;
}