fork(3) download
copy 
  1. //NickyRio
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define N 1010
  7. #define M 10010
  8. const double esp = 1e-5;
  9.  
  10. int n, m,  trace[N], u[M], v[M], c[M];
  11. double d[N];
  12.  
  13. bool Ok(int x, int y) {
  14.     while (x != 1){
  15.         x = trace[x];
  16.         if (x == 0) return false;
  17.         if (x == y) return true;
  18.     }
  19.     return false;
  20. }
  21. bool FordBellman(double mid) {
  22.     for (int i = 1; i<=n; i++) d[i] = 1e18;
  23.     d[1] = 0;
  24.     memset(trace, 0, sizeof trace);
  25.     for (int i = 0; i<n; i++) {
  26.         for (int j = 0; j<m; j++) {
  27.             int x = u[j]; int y = v[j];
  28.             if (d[y] > d[x] + c[j] - mid) {
  29.                 d[y] = d[x] + c[j] - mid;
  30.                 if (Ok(x, y)) {
  31.                     return true;
  32.                 }
  33.                 trace[y] = x;
  34.             }
  35.         }
  36.     }
  37.     return false;
  38. }
  39. int main() {
  40.     //freopen("E:\\RoadToAPIO\\CPP\\PVOI14_3\\input.txt","r",stdin);
  41.     //freopen("E:\\RoadToAPIO\\CPP\\PVOI14_3\\output.txt","w",stdout);
  42.     ios::sync_with_stdio(false);
  43.     cin.tie(0);cout.tie(0);
  44.     cin>>n>>m;
  45.     for (int i = 0; i<m; i++) {
  46.         cin>>u[i]>>v[i]>>c[i];
  47.     }
  48.     double l = 0;
  49.     double r = 1e10;
  50.     double cur = 0;
  51.     while (r - l >= esp) {
  52.         double mid = (l + r) / 2;
  53.         if (!FordBellman(mid)) {
  54.             cur = mid;
  55.             l = mid;
  56.         }else r = mid;
  57.     }
  58.     if (abs (cur - 1e10) <=esp) {
  59.         cout<<"NO TOUR";
  60.     }else
  61.     cout<<fixed<<setprecision(2)<<cur;
  62. }
  63.  
Success #stdin #stdout 0s 16192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO TOUR
https://ideone.com/TqwfeI
problem PVOI14_3, based on SPOJ submission 19590216 (CPP14), 2017-06-11 08:22:41
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!