80pts求助(Dijkstra)
查看原帖
80pts求助(Dijkstra)
704634
poor_OIer楼主2024/7/7 23:50

#1~#8AC,#9WA,#10RE求助。

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
int edges,head[2005];
double dis[2005];
int vis[2005];
struct Edge{
	int to;
	int next;
	double weight;
}edge[100005];
void add_Edge(int u,int v,double w)
{
	edges++;
	edge[edges].to=v;
	edge[edges].weight=w;
	edge[edges].next=head[u];
	head[u]=edges;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		double u,v,w;
		cin>>u>>v>>w;
		add_Edge(u,v,(100-w)/100);
		add_Edge(v,u,(100-w)/100);
	}
	cin>>a>>b;
	for(int i=1;i<=n;i++)
		dis[i]=0;
	dis[a]=1.0;
	int pos=a;
	while(!vis[pos])
	{
		long double maxx=0;
		vis[pos]=1;
		for(int i=head[pos];i;i=edge[i].next)
			if(!vis[edge[i].to]&&dis[edge[i].to]<dis[pos]*edge[i].weight)
				dis[edge[i].to]=dis[pos]*edge[i].weight;
		for(int i=1;i<=n;i++)
			if(!vis[i]&&dis[i]>maxx)
				maxx=dis[i],pos=i;
	}
	printf("%.8lf",100.0/dis[b]);
	return 0;
}
2024/7/7 23:50
加载中...