LYDSY 1486
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
#include <cstring>
const double eps = 1e-9;
template <typename T>
T max(T a, T b) { return a > b ? a : b; }
template <typename T>
T min(T a, T b) { return a < b ? a : b; }
int head[3010], next[10010], to[10010], ecnt, n, m, flag, flags[3010];
double a[10010], len[10010], dis[3010];
inline void addEdge(int x, int y)
{
ecnt++;
next[ecnt] = head[x];
head[x] = ecnt;
to[ecnt] = y;
}
bool dfs(int x)
{
if (flags[x] == flag) return true;
flags[x] = flag;
for (int cur = head[x]; cur; cur = next[cur])
if (dis[to[cur]] > dis[x] + len[cur])
{
dis[to[cur]] = dis[x] + len[cur];
if (dfs(to[cur])) return true;
}
flags[x] = 0;
return false;
}
bool check(double x)
{
for (int i = 1; i <= m; i++) len[i] = a[i] - x;
for (int i = 1; i <= n; i++)
{
flag++;
memset(dis, 0, sizeof(dis));
if (dfs(i)) return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; i++)
scanf("%d%d%lf", &x, &y, a + i), addEdge(x, y);
double l = 1e304, r = -1e304, mid;
for (int i = 1; i <= m; i++)
l = min(l, a[i]), r = max(r, a[i]);
while (r - l > eps) (check(mid = (l + r) / 2) ? r : l) = mid;
printf("%.8lf", (l + r) / 2);
return 0;
}