全wa求调
查看原帖
全wa求调
1122391
MMatthew楼主2024/9/26 23:54
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
int n, m, x, y, z, a, b;
struct node {
	int v;
	float w;
};
vector<node>e[N];
priority_queue<pair<float, int> >q;
float dis[N]; bool vis[N];
void dijkstra() {
	memset(dis, 0x3f, sizeof(dis));
	dis[a] = 1;
	q.push({ -1,a });
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();
		if (vis[u])continue;
		vis[u] = true;
		for (int i = 0, sz = e[u].size(); i < sz; i++) {
			int v = e[u][i].v;
			float w = e[u][i].w;
			if (dis[v] > dis[u] * w) {
				dis[v] = dis[u] * w;
				q.push({ -dis[v],v });
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		e[x].push_back({ y,(100 - z) / 100.0 });
		e[y].push_back({ x,(100 - z) / 100.0 });
	}
	cin >> a >> b;
	dijkstra();
	cout << fixed << setprecision(8);
	cout << 100 / dis[b];
	return 0;
}```
2024/9/26 23:54
加载中...