求助!!!想不明白哪里错了
查看原帖
求助!!!想不明白哪里错了
851870
zbk_ning楼主2024/3/14 21:57




#include<bits/stdc++.h>
using namespace std;


typedef pair <double,int> PDI;
const int N = 2010,M=5000,INF = 0x3f3f3f3f;
int n,p,m;
int cow[N];
int h[N],e[M],ne[M],idx;
int st[N];
double dist[N],w[N];
int S,T;

void add (int a,int b,int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}



double dijkstra(){
	memset(dist,0.0,sizeof dist);
	priority_queue<PDI> heap;
	heap.push({1.0,S});
	dist[S]=1.0;		
	while(heap.size()){
		PDI 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(dist[j]<dist[ver]*w[i]){
				dist[j]=dist[ver]*w[i];
				heap.push({dist[j],j});
			}
		}
		
	}
	
	return dist[T];
}







int main(){
	
	memset(h,-1,sizeof h);
	cin>>n>>m;
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		double cc=1-c/100;
		add(a,b,cc),add(b,a,cc);
	}
	
	cin>>S>>T;
	printf("%.8lf",100/dijkstra());
	
	
}











2024/3/14 21:57
加载中...