mickypinata

OJ-T00104: Arbitrage

Dec 6th, 2021 (edited)
543
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 20 + 5;
  5.  
  6. double dist[N][N][N];
  7. int pr[N][N][N];
  8.  
  9. int main(){
  10.  
  11.     int nVertex;
  12.     while(scanf("%d", &nVertex) != EOF){
  13.         for(int u = 1; u <= nVertex; ++u){
  14.             for(int v = 1; v <= nVertex; ++v){
  15.                 if(u == v){
  16.                     dist[1][u][u] = 0;
  17.                 } else {
  18.                     scanf("%lf", &dist[1][u][v]);
  19.                     dist[1][u][v] = -log(dist[1][u][v]);
  20.                 }
  21.                 pr[1][u][v] = u;
  22.             }
  23.         }
  24.         for(int c = 2; c <= nVertex; ++c){
  25.             for(int u = 1; u <= nVertex; ++u){
  26.                 for(int v = 1; v <= nVertex; ++v){
  27.                     dist[c][u][v] = 1e308;
  28.                 }
  29.             }
  30.         }
  31.         for(int c = 2; c <= nVertex; ++c){
  32.             for(int k = 1; k <= nVertex; ++k){
  33.                 for(int u = 1; u <= nVertex; ++u){
  34.                     for(int v = 1; v <= nVertex; ++v){
  35.                         if(dist[c - 1][u][k] + dist[1][k][v] < dist[c][u][v]){
  36.                             dist[c][u][v] = dist[c - 1][u][k] + dist[1][k][v];
  37.                             pr[c][u][v] = k;
  38.                         }
  39.                     }
  40.                 }
  41.             }
  42.         }
  43.         double tr = -log(1.01);
  44.         int cnt = 0;
  45.         int st = 0;
  46.         for(int c = 2; c <= nVertex; ++c){
  47.             for(int u = 1; u <= nVertex; ++u){
  48.                 if(dist[c][u][u] < tr){
  49.                     cnt = c;
  50.                     st = u;
  51.                     goto printPath;
  52.                 }
  53.             }
  54.         }
  55.         cout << "no arbitrage sequence exists\n";
  56.         continue;
  57.         printPath:
  58.         stack<int> stk;
  59.         int cur = st;
  60.         stk.push(st);
  61.         for(; cnt >= 1; --cnt){
  62.             cur = pr[cnt][st][cur];
  63.             stk.push(cur);
  64.         }
  65.         while(stk.size() > 1){
  66.             cout << stk.top() << ' ';
  67.             stk.pop();
  68.         }
  69.         cout << stk.top() << '\n';
  70.     }
  71.  
  72.     return 0;
  73. }
  74.  
RAW Paste Data