Dij,0pts,大佬求调
查看原帖
Dij,0pts,大佬求调
772478
Wisdom_chicken_god楼主2023/8/10 14:12
#include<bits/stdc++.h>
#define M 200005
using namespace std;
int n,m,s,A,B;
priority_queue<pair<double ,int> >q;
int qnext[M],ver[M],head[M],num;
bool b[M];
double dis[M],tance[M];
void add(int fr,int to,double di)
{
	dis[++num]=di;
	ver[num]=to;
	qnext[num]=head[fr];
	head[fr]=num;
}
void Dij(int u)
{
	for(int i=1;i<=m;i++)
	tance[i]=-1*1.00;
	tance[u]=1.00;
	q.push(make_pair(1.00,u));
	while(q.size())
	{
		int cnt;
		cnt=q.top().second;
		q.pop();
		if(b[cnt]==1)
		continue;
		b[cnt]=1;
		for(int i=head[cnt];i;i=qnext[i])
		{
			int y=ver[i];
			double z=dis[i];
			if(tance[y]<tance[cnt]*z*1.00)
			tance[y]=tance[cnt]*z*1.00;
			q.push(make_pair(-tance[y],y));
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int  x,y;
		double d;
		scanf("%d%d%lf",&x,&y,&d);
		add(x,y,1-0.01*d);
		add(y,x,1-0.01*d);
	}
	scanf("%d%d",&A,&B);
	Dij(A);
	double ff=100/tance[B];
	printf("%.8lf",ff);
	return 0;
}
2023/8/10 14:12
加载中...