不带优化的 Dijkstra 求调
查看原帖
不带优化的 Dijkstra 求调
742157
ZYK_luogu楼主2023/8/11 08:19
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 2010;
struct Edge {
	int v;
	double w;
};
int n, m, x, y, z, dis[N], vis[N];
vector<Edge> p[N];
void Dijkstra(int s) {
	for(int i = 1; i <= n; i ++)
		dis[i] = 1e9;
	dis[s] = 1;
	for(int i = 0; i < n; i ++) {
		int k = -1;
		for(int j = 1; j <= n; j ++)
			if(!vis[j] && (k == -1 || dis[j] < dis[k]))
				k = j;
		vis[k] = 1;
		for(int j = 0, siz = p[k].size(); i < siz; i ++) {
			int v = p[k][j].v;
			double w = p[k][i].w;
			if(dis[v] < dis[k] * w) 
				dis[v] = dis[k] * w;
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i ++) {
		scanf("%d%d%d", &x, &y, &z);
		p[x].push_back({y, 1 - 0.01 * z});
		p[y].push_back({x, 1 - 0.01 * z});
	}
	int A, B;
	scanf("%d%d", &A, &B);
	Dijkstra(A);
	printf("%.8lf", 1.0 * 100 / dis[B]);
	return 0;
}
2023/8/11 08:19
加载中...