AcWing 361. 观光奶牛
原题链接
中等
作者:
MILLOPE
,
2019-05-11 15:09:27
,
所有人可见
,
阅读 1196
题解
题解传送门
code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 100;
const int maxm = 1e4 + 100;
const int eps = 1e-5;
template <typename T>
inline void read(T &s) {
s = 0;
T w = 1, ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
s *= w;
}
int n, m, tot;
int lin[maxn], nex[maxm], edge[maxm], ver[maxm], val[maxn], cnt[maxn];
bool vis[maxn];
double dis[maxn];
inline void add(int from, int to, int dis) {
ver[++tot] = to;
edge[tot] = dis;
nex[tot] = lin[from];
lin[from] = tot;
}
bool spfa(double ans) {
queue <int> q;
for (int i = 1; i <= n; ++i) {
q.push(i);
cnt[i] = 1;
vis[i] = true;
dis[i] = 0.0;
}
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = false;
for (int i = lin[u]; i; i = nex[i]) {
int v = ver[i];
if (dis[v] > dis[u] + edge[i] * ans - (double)val[u]) {
dis[v] = dis[u] + edge[i] * ans - (double)val[u];
if (!vis[v]) {
vis[v] = true;
q.push(v);
cnt[v]++;
if (cnt[v] >= n) return true;
}
}
}
}
return false;
}
int main() {
read(n), read(m);
for(int i = 1; i <= n; ++i)
read(val[i]);
for (int i = 1; i <= m; ++i) {
int x, y, z;
read(x), read(y), read(z);
add(x, y, z);
}
double l = 0, r = 1e5 + 1;
for (int i = 1; i <= 100; ++i) {
double mid = (l + r) / 2.0;
if (spfa(mid)) l = mid;
else r = mid;
}
printf("%.2lf", l * 1.0);
return 0;
}