fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <fstream>
  3.  
  4. #define int long long
  5.  
  6. #define TASK "minpath"
  7.  
  8. using namespace std;
  9.  
  10. const int MAXN = 1e2 + 7, oo = 3e18;
  11.  
  12. int N, M, K;
  13. int G[MAXN][MAXN];
  14.  
  15. struct Matrix {
  16.     int M, N;
  17.     vector < vector < int > > v;
  18.  
  19.     Matrix(int row = 0, int col = 0, int val = 0) {
  20.         M = row;
  21.         N = col;
  22.         v.assign(M, vector <int> (N, val));
  23.     }
  24.  
  25.     Matrix operator * (const Matrix &A) {
  26.         int P = A.N;
  27.         Matrix res(M, P, +oo);
  28.  
  29.         for (int i = 0; i < M; ++i) {
  30.             for (int j = 0; j < P; ++j) {
  31.                 for (int k = 0; k < N; ++k) {
  32.                     res.v[i][j] = min(res.v[i][j], v[i][k] + A.v[k][j]);
  33.                 }
  34.             }
  35.         }
  36.  
  37.         return res;
  38.     }
  39.  
  40.     Matrix operator ^ (int k) const {
  41.         Matrix res(N, N, +oo);
  42.         for (int i = 0; i < N; ++i) {
  43.             for (int j = 0; j < N; ++j) {
  44.                 if (i == j)
  45.                     res.v[i][j] = 0;
  46.             }
  47.         }
  48.         Matrix mul = *this;
  49.  
  50.         while (k) {
  51.             if (k & 1) res = res * mul;
  52.             mul = mul * mul;
  53.             k >>= 1;
  54.         }
  55.  
  56.         return res;
  57.     }
  58. };
  59.  
  60. int ANS = +oo;
  61.  
  62. main() {
  63.     ios_base::sync_with_stdio(0);
  64.     cin.tie(NULL);
  65.     cout.tie(NULL);
  66.  
  67. #ifndef ONLINE_JUDGE
  68. 	freopen(TASK".inp", "r", stdin);
  69. 	freopen(TASK".out", "w", stdout);
  70. #endif
  71.  
  72.     cin >> N >> M >> K;
  73.     Matrix A(N, N, +oo);
  74.     for (int i = 1; i <= M; ++i) {
  75.         int u, v, c;
  76.         cin >> u >> v >> c;
  77.         A.v[u - 1][v - 1] = c;
  78.     }
  79.  
  80.     Matrix res(1, N, 0);
  81.  
  82.     res = res * (A ^ K);
  83.  
  84.     for (int i = 0; i < N; ++i) {
  85.         ANS = min(ANS, res.v[0][i]);
  86.     }
  87.  
  88.     if (ANS < (+oo) / 2)
  89.         cout << ANS << '\n';
  90.     else
  91.         cout << "IMPOSSIBLE" << '\n';
  92.  
  93. }
  94.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IMPOSSIBLE
https://ideone.com/IrO5Au
language:
C++ (gcc 8.3)
created:
30 days ago
visibility:
public

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!