样例没过,不知哪里有问题,请dalao帮助
查看原帖
样例没过,不知哪里有问题,请dalao帮助
797354
Ferdina_zcjb楼主2023/3/31 19:39
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x7fffffff
ll n ,m,h[100000],cnt,vis[1000000];
double d[100000];
struct node{
	ll to,next;
	double data;
}w[1000000];
void add(int a , int b , double c){
	++cnt;
	w[cnt].to = b;
	w[cnt].next = h[a];
	w[cnt].data = c;
	h[a] = cnt;
}
void Dijkstra(ll v0){
	double minn;
	ll tmp;
	memset(vis,0,sizeof(vis));
	for(int i = 1;i <= n;++i){
		d[i] = INF;
	}
	d[v0] = 1.0;
	for(int i = 1;i <= n;++i){
		minn = INF;
		for(int j = 1;j <= n;++j){
			if(!vis[j]&&minn > d[j]){
				tmp = j;
				minn = d[j];
			}
		}
		vis[tmp] = 1;
		for(int j = h[tmp];j;j = w[j].next){
			int kkk = w[j].to;
			if(!vis[kkk]&&d[tmp]*w[j].data< d[kkk]){
				d[kkk] = d[tmp]*w[j].data;
			}
		} 
	}
}
int main(){
	cin >> n >> m;
	for(ll i = 1;i <= m;++i){
		int a , b;
		int c;
		cin >>a >> b >> c;
		add(a , b , 1.0 - c / 100.0);
		add(b , a , 1.0 - c / 100.0);
	}
	ll A,B;
	cin >> A >> B;
	Dijkstra(A);
	printf("%.8lf",100.0 / d[B]);
	return 0;
}
2023/3/31 19:39
加载中...