样例未过求调。。。(要死啦
查看原帖
样例未过求调。。。(要死啦
1065103
Atri_Lobato楼主2024/4/11 17:31
#include<iostream>
#include<cstring>
using namespace std;
double tax[3005][3005];
double ans[200005];
int ed[2000005]={0};
int m,n,k;
int x,y;
void dijkstra(int start)
{
	memset(ans,128,sizeof(ans));
	for(int i=1;i<=n;i++)
	{
		ans[i]=tax[start][i];
	}
	ans[start]=1;
	ed[start]=1;
	for(int i=1;i<=n-1;i++)
	{
		int maxn=0;
//		int k=0;
		for(int q=1;q<=n;q++)
		{
			if(ed[q]==0&&maxn<ans[q])
			{
				k=q;
				maxn=ans[q];
			}
		}
		ed[k]=1;
		if(k==y)
		break;
		for(int q=1;q<=n;q++)
		{
			if(tax[k][q]*ans[k]>ans[q])
			{
				ans[q]=tax[k][q]*ans[k];
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		double c;
		scanf("%d%d%lf",&a,&b,&c);
		double t=(100.0-c)/100.0;
		tax[a][b]=t;
		tax[b][a]=t;
	}
//	int x,y;
	scanf("%d%d",&x,&y);
	dijkstra(x);
	printf("%.8lf",100.0/ans[y]);
	return 0;
}
2024/4/11 17:31
加载中...