40pts求条
查看原帖
40pts求条
1047636
_ScreamBrother_楼主2024/8/14 18:06
#include <bits/stdc++.h>
using namespace std;
#define double long double

double G[2510][2510], d[2510], w;
int N, M, S, T, u, v;
bool vis[2510] = {};

void Dijkstra() {
	vis[S] = true;
	for (int i = 1; i <= N; i ++) d[i] = G[S][i];
	d[1] = 1;
	for (int i = 1; i < N; i ++) {
		int n = 0;
		double m = -1;
		for (int j = 1; j <= N; j ++)
			if (!vis[j] && d[j] > m) n = j, m = d[j];
		
		vis[n] = true;
		
		for (int j = 1; j <= N; j ++)
			if (!vis[j] && m * G[n][j] > d[j])
				d[j] = m * G[n][j];
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	
	cin >> N >> M;
	for (int i = 1; i <= M; i ++) {
		cin >> u >> v >> w;
		double W = 1.0 * (100 - w) / 100.0;
		G[u][v] = W, G[v][u] = W;
	}
	for (int i = 1; i <= N; i ++) G[i][i] = 1;
	cin >> S >> T;
	
	Dijkstra();
	cout << fixed << setprecision(8) << 100.0 / d[T];
	
	return 0;
}
2024/8/14 18:06
加载中...