Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // by tmt514
- #include <algorithm>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <string>
- #include <vector>
- #define SZ(x) ((int)(x).size())
- #define FOR(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
- using namespace std;
- typedef long long LL;
- const int N = 5005;
- const int M = 100005;
- int s[M], t[M], c[M], p[M], q[M];
- #include <iomanip>
- #include <queue>
- #include <cassert>
- //#define NDEBUG
- //int Q[5000005], qb, qe;
- #include <queue>
- priority_queue<pair<double, int>> PQ;
- void solve() {
- int n, m;
- vector<int> a[N];
- const double INF = 1e9;
- double d[N];
- scanf("%d%d", &n, &m);
- assert(m <= 100000);
- for(int i=0;i<m;i++) {
- scanf("%d%d%d%d%d", &s[i], &t[i], &c[i], &p[i], &q[i]);
- assert(1 <= s[i] && s[i] <= n);
- assert(1 <= t[i] && t[i] <= n);
- assert(1 <= c[i] && c[i] <= 100);
- assert(1 <= p[i] && p[i] <= 100);
- assert(1 <= q[i] && q[i] <= 100);
- assert(s[i] != t[i]);
- a[s[i]].push_back(i);
- a[t[i]].push_back(i);
- }
- for(int x=1;x<=n;x++) {
- d[x] = INF;
- for(auto i: a[x]) {
- int pmiss = 100 - (x == s[i]? p[i]: q[i]);
- int qmiss = 100 - (x == s[i]? q[i]: p[i]);
- d[x] = min(d[x], c[i] * (10000 + 100 * pmiss) / (double)(10000 - pmiss * qmiss));
- }
- }
- bool mark[N] = {};
- //qb = qe = 0;
- for(int x=1;x<=n;x++) { mark[x] = 1; PQ.push({ -d[x], x }); }
- while (!PQ.empty()) {
- auto pp = PQ.top();
- PQ.pop();
- int x = pp.second;
- //int x = Q[qb++];
- mark[x] = false;
- for(auto i : a[x]) {
- int y = (x==s[i]? t[i]: s[i]);
- int pmiss = 100 - (x == s[i]? p[i]: q[i]);
- double v = c[i] + pmiss / 100.0 * d[y];
- if (d[x] > v) d[x] = v;
- }
- for(auto i : a[x]) {
- int y = (x==s[i]? t[i]: s[i]);
- int qmiss = 100 - (x == s[i]? q[i]: p[i]);
- double v = c[i] + qmiss / 100.0 * d[x];
- if (d[y] > v) {
- d[y] = v;
- if (mark[y] == false) {
- mark[y] = true;
- PQ.push({ -d[y], y });
- //Q[qe++] = y;
- }
- }
- }
- }
- for(int i=0;i<m;i++) {
- int x = s[i], y = t[i];
- //fprintf(stderr, "x=%d (%.6Lf), y=%d (%.6Lf), (c=%d, p=%d, q=%d)\n", x, d[x], y, d[y], c[i], p[i], q[i]);
- assert(d[x] <= c[i] + (100-p[i]) / 100.0 * d[y]);
- assert(d[y] <= c[i] + (100-q[i]) / 100.0 * d[x]);
- }
- cout << fixed << setprecision(6) << d[1] << endl;
- }
- int main(void) {
- int T;
- srand(0);
- scanf("%d", &T);
- while(T--) solve();
- return 0;
- }
Add Comment
Please, Sign In to add comment