为什么错了
查看原帖
为什么错了
851870
zbk_ning楼主2023/11/27 22:10
#include<bits/stdc++.h>
using namespace std;


const int maxn = 1e6+5;
const int mod = 100003;
vector<int> g[maxn]; 
double rate[maxn]; 
int cnt[maxn];
int st[maxn];
int sx,ex;
typedef pair<double, int> PII;
int n, m; 
double w[maxn];
int h[maxn], e[maxn], ne[maxn], idx;//邻接表存储图
void add(int a,int b,double c){
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}



void dijkstra(){
	memset(rate,-0x3f,sizeof rate);
	rate[1]=1.0;
	priority_queue<PII,vector<PII>,less<PII> >heap;
	heap.push({1.0,sx});//换算率 人的标号
	while(heap.size()){
		PII t=heap.top();
		heap.pop();
		int ver=t.second;
		if(st[ver]) continue;
		st[ver]=1;
		for(int i=h[ver];i!=-1;i=ne[i]){
			int j=e[i];
			if(rate[j]<rate[ver]*w[i]){
				rate[j]=rate[ver]*w[i];
				heap.push({rate[j],j});
			}
		}
	} 
}





int main(){
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--){
		int x,y;
		double z;
		cin>>x>>y>>z;
		double r=1-z/100;
		add(x,y,r);add(y,x,r);
	}
	cin>>sx>>ex;
	dijkstra();
	
	
	printf("%.8lf",100/rate[ex]);
}















2023/11/27 22:10
加载中...