求助!!样例过了但0分
查看原帖
求助!!样例过了但0分
1094053
Fisher2008楼主2024/4/21 17:13
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
using namespace std;
double a[2001][2001],dis[2001]={0},maxn;
int n,m,i,j,k,x,y,f[2001]={0};

void init()
{
	cin>>n>>m;//n个点,m条边(n人,m对可以相互转账) 
	for(i=1;i<=m;i++)
	{
		cin>>j>>k;
		cin>>a[j][k];// 不可以  cin>>j>>k>>a[j][k];
		a[j][k]=(100-a[j][k])/100;
		a[k][j]=a[j][k]; 
	}
	cin>>x>>y;
}

void dijkstra(int x)
{
	for(i=1;i<=n;i++) dis[i]=a[x][i];
	dis[x]=1;
	f[x]=1;
	for(i=1;i<=n-1;i++)
	{
		maxn=0;
		for(j=1;j<=n;j++)  if(f[j]==0 && dis[j]>maxn) {k=j;maxn=dis[j];}
		f[k]=1;
		if(k==y)  break;
		for(j=1;j<=n;j++)  if(f[j]==0 && dis[k]*a[k][j]>dis[j])  dis[j]=dis[k]*a[k][j];		
	}	
}

int main()
{
	init();
	dijkstra(x);
	printf("%.81f",100/dis[y]);
	return 0;
}

2024/4/21 17:13
加载中...