Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- using namespace std;
- const int N = 1e3 + 5;
- const double vc = (double)(1e15);
- const double eps = 1e-3;
- int n, m;
- vector < pair < int , int > > adj[N];
- double d[N];
- bool flag = false;
- int visit[N];
- void dfs(int u) {
- visit[u] = 1;
- for (auto it : adj[u]) {
- int v = it.first;
- if (visit[v] == 1) flag = true;
- if (visit[v] == 0) dfs(v);
- }
- visit[u] = 2;
- }
- bool cycle() {
- for (int i = 1; i <= n; i++)
- if (!visit[i]) dfs (i);
- return flag;
- }
- bool shimbel(double val) {
- for (int i = 1; i <= n; i++) d[i] = vc;
- d[1] = 0;
- for (int i = 1; i < n; i++)
- for (int u = 1; u <= n; u++)
- for (auto it : adj[u]) {
- int v = it.first, w = it.second;
- if (d[u] > d[v] + w - val) {
- d[u] = d[v] + w - val;
- }
- }
- for (int u = 1; u <= n; u++)
- for (auto it : adj[u]) {
- int v = it.first, w = it.second;
- if (d[u] > d[v] + w - val)
- return false;
- }
- return true;
- }
- int main() {
- scanf ("%d %d", &n, &m);
- for (int i = 0; i < m; i++) {
- int u, v, w;
- scanf ("%d %d %d", &u, &v, &w);
- adj[u].push_back({v, w});
- }
- if (!cycle()) {
- printf("-1\n");
- return 0;
- }
- double d = 0, c = vc, res = -1;
- while (d <= c) {
- double g = (d + c) / 2;
- if (shimbel(g)) {
- res = g;
- d = g + eps;
- } else c = g - eps;
- }
- printf("%.2f\n", res);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement