• API
• FAQ
• Tools
• Archive
daily pastebin goal
61%
SHARE
TWEET

# Untitled

a guest Sep 14th, 2018 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <algorithm>
3. #include <vector>
4. using namespace std;
5.
6. const int N = 1e3 + 5;
7. const double vc = (double)(1e15);
8. const double eps = 1e-3;
9.
10. int n, m;
11. vector < pair < int , int > > adj[N];
12. double d[N];
13. bool flag = false;
14. int visit[N];
15.
16. void dfs(int u) {
17.     visit[u] = 1;
18.     for (auto it : adj[u]) {
19.         int v = it.first;
20.         if (visit[v] == 1) flag = true;
21.         if (visit[v] == 0) dfs(v);
22.     }
23.     visit[u] = 2;
24. }
25.
26. bool cycle() {
27.     for (int i = 1; i <= n; i++)
28.         if (!visit[i]) dfs (i);
29.     return flag;
30. }
31.
32. bool shimbel(double val) {
33.     for (int i = 1; i <= n; i++) d[i] = vc;
34.     d[1] = 0;
35.
36.     for (int i = 1; i < n; i++)
37.         for (int u = 1; u <= n; u++)
38.             for (auto it : adj[u]) {
39.                 int v = it.first, w = it.second;
40.                 if (d[u] > d[v] + w - val) {
41.                     d[u] = d[v] + w - val;
42.                 }
43.             }
44.
45.     for (int u = 1; u <= n; u++)
46.         for (auto it : adj[u]) {
47.             int v = it.first, w = it.second;
48.             if (d[u] > d[v] + w - val)
49.                 return false;
50.         }
51.
52.     return true;
53. }
54.
55. int main() {
56.     scanf ("%d %d", &n, &m);
57.     for (int i = 0; i < m; i++) {
58.         int u, v, w;
59.         scanf ("%d %d %d", &u, &v, &w);
61.     }
62.
63.     if (!cycle()) {
64.         printf("-1\n");
65.         return 0;
66.     }
67.
68.     double d = 0, c = vc, res = -1;
69.     while (d <= c) {
70.         double g = (d + c) / 2;
71.         if (shimbel(g)) {
72.             res = g;
73.             d = g + eps;
74.         } else c = g - eps;
75.     }
76.
77.     printf("%.2f\n", res);
78.
79.     return 0;
80. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top