样例已过,全WA
查看原帖
样例已过,全WA
524782
2_6HogCycle楼主2021/12/2 18:00
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100001; 
queue<int>que;
int n,m,a,b,w,END,visit[MAXN/5],cnt,START,dic;double dis[MAXN/5];double head[MAXN/5];
int cur,nextpoint;
struct edge{
	int to;
	int next;
	double weight;
}edge[MAXN];
void add(int a,int b,double v)
{
	edge[++cnt].next=head[a];
	edge[cnt].weight=1-v/100;
	edge[cnt].to=b;
	head[a]=cnt;
}
int main(){	
	scanf("%d%d",&n,&m);
	fill(dis+1,dis+n+1,0);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&w);
		add(a,b,w);
		add(b,a,w);
	}
	scanf("%d%d",&START,&END);
	dis[START]=1;
	que.push(START);
	visit[START]=1;
	while(!que.empty())
	{
		cur=que.front();
		que.pop();
		visit[cur]=0;
		for(int i=head[cur];i;i=edge[i].next)
		{
			nextpoint=edge[i].to;
			if(dis[nextpoint]<dis[cur]*edge[i].weight)
			{
				dis[nextpoint]=dis[cur]*edge[i].weight;
				if(visit[nextpoint]==0)
				{
					que.push(nextpoint);
					visit[nextpoint]=1;
				}
			}
		}
	}
	printf("%.8lf",100/dis[END]);
	return 0;
}

2021/12/2 18:00
加载中...