【題解】Codeforces GYM 102644F. Min Path

#include <iostream>
using namespace std;
 
long long n, m, k, x, y, w, a[105][105], ans[105], mod = 1e9+7, inf = 0x3F3F3F3F3F3F3F3F;
 
int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            a[i][j] = inf;
        }
    }
    for (int i = 0; i < m; i++){
        cin >> x >> y >> w;
        x--;
        y--;
        a[y][x] = w;
    }
    while (k){
        if (k & 1){
            long long tmp[105] = {};
            for (int i = 0; i < n; i++){
                tmp[i] = inf;
                for (int k = 0; k < n; k++){
                    tmp[i] = min(tmp[i], a[i][k]+ans[k]);
                }
            }
            for (int i = 0; i < n; i++){
                ans[i] = tmp[i];
            }
        }
        long long tmp[105][105] = {};
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                tmp[i][j] = inf;
                for (int k = 0; k < n; k++){
                    tmp[i][j] = min(tmp[i][j], a[i][k]+a[k][j]);
                }
            }
        }
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                a[i][j] = tmp[i][j];
            }
        }
        k >>= 1;
    }
    for (int i = 1; i < n; i++){
        ans[0] = min(ans[0], ans[i]);
    }
    if (ans[0] > 1e18) cout << "IMPOSSIBLE\n";
    else cout << ans[0] << "\n";
}