10pts求调(玄关)
查看原帖
10pts求调(玄关)
741578
hhhh2971楼主2024/7/26 15:23
#include<bits/stdc++.h>
using namespace std;

int juli[2005][2005];
bool vis[2005];
double dis[2005];
struct Node
{
	int st,en,c;
}a[100005];

int main()
{
	int n,m;
	cin >> n >> m;
	for (int i=1;i<=n;i++)
		dis[i]=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			juli[i][j]=1000;
	for (int i=1;i<=m;i++)
	{
		cin >> a[i].st >> a[i].en >> a[i].c;
		juli[a[i].st][a[i].en]=a[i].c;
		juli[a[i].en][a[i].st]=a[i].c;
	}
	int shuchu,jieqian;
	cin >> shuchu >> jieqian;
	for (int i=1;i<=m;i++)
	{
		if (a[i].st==shuchu) dis[a[i].en]=1.0-1.0*a[i].c/100;
		if (a[i].en==shuchu) dis[a[i].st]=1.0-1.0*a[i].c/100;
	}
	vis[shuchu]=true;
	dis[shuchu]=1;
	for (int i=1;i<n;i++)
	{
		double minn=0;
		int ans=0;
		for (int j=1;j<=n;j++)
			if (!vis[j] && dis[j]>minn)
			{
				minn=dis[j];
				ans=j;
			}
		vis[ans]=true;
		if (ans==0) break;
		for (int j=1;j<=m;j++)
			if (juli[ans][j]!=1000)
				dis[j]=max(dis[j],dis[ans]*(1.0-1.0*juli[ans][j]/100));
	}
	printf("%.8lf\n",100.0/dis[jieqian]);
	
	return 0;
}
2024/7/26 15:23
加载中...