求助!样例过,结果全WA
查看原帖
求助!样例过,结果全WA
716721
leo12334楼主2023/1/10 20:26

求助各位大佬,能否帮忙看看哪里出的问题QWQ

#include<bits/stdc++.h>
using namespace std;
#define mp(x,y) make_pair(x,y)
#define pii pair<double,int>
#define N 2001
struct node{
	int next,to,w;
}e[100010];
int n,m,cnt,st,ed,arr[N],vis[N],head[N],x,y,w;
double dis[N];
void add(int x,int y,int w){
	e[++cnt].to=y;
	e[cnt].next=head[x];
	e[cnt].w=w;
	head[x]=cnt;
}
void dijiesitela(){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)dis[i]=0.0;//dis表示保留的比例 ,越大越好 
	dis[st]=1.0;
	priority_queue< pii >q;
	q.push(mp(1.0,st));
	while(q.size()){
		int x=q.top().second;q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].to,v=e[i].w;
			if(dis[y]<dis[x]*(1-e[i].w*0.01)){
				dis[y]=dis[x]*(1-e[i].w*0.01);
				q.push(mp(-dis[y],y));
			}
		}
	}
}
int main(){
	cin>>n>>m;
	while(m--){
		cin>>x>>y>>w;
		add(x,y,w);
		add(y,x,w);
	}
	cin>>st>>ed;
	dijiesitela();
	printf("%.8lf\n",100/dis[ed]);
}
2023/1/10 20:26
加载中...