求助,样例过 全WA
查看原帖
求助,样例过 全WA
753810
Cheese_int楼主2022/10/19 19:32
#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read () {
	int w = 0, f = 1; char ch = getchar ();
	while (ch < '0' || ch > '9') {if (ch == '-') f = -1 ; ch = getchar ();}
	while (ch >= '0' && ch <= '9') {w = (w << 3) + (w << 1) + ch - '0'; ch = getchar ();}
	return w * f;
}

struct Graph {
	double ds[100005];
	int vs[100005];
	vector <int> E[100005];
	vector <double> V[100005];
	priority_queue <pair <double, int>, vector <pair <double, int> >, greater <pair <double, int> > > PQ;
	
	void push (int x, int y, double z) {
		E[x].push_back (y);
		V[x].push_back (z);
	}
	
	void dij (int s) {
		memset (ds, -145, sizeof (ds));
		memset (vs, 0, sizeof (vs));
		ds[s] = 100.00;
		PQ.push (make_pair (ds[s], s));
		while (PQ.size ()) {
			int nw = PQ.top ().second;
			PQ.pop (); 
			if (vs[nw] == 1) continue;
			vs[nw] = 1;
			for (int i = 0; i < E[nw].size (); i++) {
				int k = E[nw][i];
				double w = V[nw][i];
				if (ds[k] > (double)((ds[nw]) / (1 - w / 100))) {
					ds[k] = (double)((ds[nw]) / (1 - w / 100));
					PQ.push (make_pair (ds[k], k));	
				}
				
			}
		}
	}
	
}G;

int n, m, b;

signed main () {
	n = read (), m = read ();
	int x, y;
	double z;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y >> z;
        G.push (x, y, z);
		G.push (y, x, z);
	}
	G.dij (n);
	printf ("%.8lf", G.ds[1]);
	return 0;
}

哎呀

2022/10/19 19:32
加载中...