problem source

我猜了个结论。
定义新的矩阵乘法，假设 $a \cdot b = c$，那么 $c_{i,j} = \min\limits_{k=1}^n (a_{i,k}+b_{k,j})$

然后正常矩阵快速幂，就 AC 了，有 dalao 能讲讲正确性吗？

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
const int maxn=105;
int n,m,k;
int T;
struct Matrix{
    ll mp[maxn][maxn];
    void init(){
        FOR(i,0,100){
            FOR(j,0,100)mp[i][j]=3e18;
        }
    }
    void unit(){
        init();
        FOR(i,0,100)mp[i][i]=0;
    }
    Matrix operator*(const Matrix& b)const{
        Matrix res;
        res.init();
        FOR(i,1,100){
            FOR(k,1,100){
                FOR(j,1,100){
                    ckmn(res.mp[i][j],mp[i][k]+b.mp[k][j]);
                }
            }
        }
        return res;
    }
    Matrix power(int k){
        Matrix base=*this;
        Matrix res;
        res.unit();
        for(;k;base=base*base,k>>=1){
            if(k&1)res=res*base;
        }
        return res;
    }
};
void solve(){
    scanf("%d%d%d",&n,&m,&k);
    Matrix mul;
    mul.init();
    FOR(i,1,m){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        ckmn(mul.mp[b][a],1ll*c);
    }
    mul=mul.power(k);
    ll ans=4e18;
    FOR(i,1,n){
        FOR(j,1,n){
            ckmn(ans,mul.mp[i][j]);
        }
    }
    if(ans>2e18){
        puts("IMPOSSIBLE");
    }
    else printf("%lld\n",ans);
}
int main()
{
	T=1;
	while(T--){
		solve();
	}
	return 0;
}