1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
| #include <iostream> #include <cstdio> #include <queue> using namespace std; const double eps = 1e-4; const int N = 1e3 + 10, M = 5e3 + 10; double d[N]; bool vis[N]; int n, m, cnt[N], f[N]; int idx = -1, hd[N], nxt[M], edg[M], wt[M]; bool check(double mid) { for (int i = 1; i <= n; i++) d[i] = cnt[i] = 0; queue <int> q; for (int i = 1; i <= n; i++) { q.push(i); vis[i] = true; } while (!q.empty()) { int t = q.front(); q.pop(); vis[t] = false; for (int i = hd[t]; ~i; i = nxt[i]) if (d[t] + f[t] - mid * wt[i] > d[edg[i]]) { d[edg[i]] = d[t] + f[t] - mid * wt[i]; cnt[edg[i]] = cnt[t] + 1; if (cnt[edg[i]] >= n) return true; if (!vis[edg[i]]) { q.push(edg[i]); vis[edg[i]] = true; } } } return false; } void add(int x, int y, int z) { nxt[++idx] = hd[x]; hd[x] = idx; edg[idx] = y; wt[idx] = z; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) hd[i] = -1; for (int i = 1; i <= n; i++) cin >> f[i]; for (int i = 1, a, b, c; i <= m; i++) { cin >> a >> b >> c; add(a, b, c); } double l = 0, r = N, mid; while (r - l > eps) { mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } printf("%.2lf", l); return 0; }
|
Gitalk 加载中 ...