daily pastebin goal
28%
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);
  60.         adj[u].push_back({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. OK, I Understand
 
Top