没过样例,大佬求调
查看原帖
没过样例,大佬求调
941502
_Gabriel_楼主2023/7/13 12:14
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int h[N], vtx[2 * N], nxt[2 * N], idx;
double dis[N], wt[2 * N];
int pre[N], vis[N];
int n, m, s, t, tu, tv;
double tw;

struct node {
	int u, v, w;
	friend bool operator < (node a, node b) {
		if (a.w >= b.w) {
			return 1;
		} else {
			return 0;
		}
	}
};
priority_queue <node> q;

void addEdge(int a, int b, int c) {
	vtx[idx] = b;
	nxt[idx] = h[a];
	wt[idx] = 1.0 - c / 100.0;
	h[a] = idx++;
}

void dijkstra(int s) {
	dis[s] = 0;
	node tmp;
	tmp.u = s;
	tmp.v = s;
	tmp.w = 0;
	q.push(tmp);
	while (!q.empty()) {
		tmp = q.top();
		q.pop();
		int nid = tmp.v;
		if (vis[nid] == 1) {
			continue;
		}
		vis[nid] = 1;
		int p = h[nid];
		while (p != -1) {
			if (vis[vtx[p]] == 0) {
				if (dis[nid] + wt[p] < dis[vtx[p]]) {
					dis[vtx[p]] = dis[nid] + wt[p];
					pre[vtx[p]] = nid;
					tmp.u = nid;
					tmp.v = vtx[p];
					tmp.w = dis[vtx[p]];
					q.push(tmp);
				}
			}
			p = nxt[p];
		}
	}
}
int main() {
	cin >> n >> m; 
	for (int i = 1; i <= m; i++) {
		dis[i] = INF;
	}
	memset(h, -1, sizeof(h));
	while (m--) {
		cin >> tu >> tv >> tw;
		addEdge(tu, tv, tw);
		addEdge(tv, tu, tw); 
	}
	cin >> s >> t;
	dijkstra(s);
	cout << fixed << setprecision(8) << 100.0 / dis[t];
	return 0;
} 
2023/7/13 12:14
加载中...