POJ 3613

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <string>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
// #include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ull, ull> puu;

#define inf (0x3f3f3f3f)
#define lnf (0x3f3f3f3f3f3f3f3f)
#define eps (1e-9)
#define fi first
#define se second

bool sgn(double a, string select, double b) {
    if(select == "==")return fabs(a - b) < eps;
    if(select == "!=")return fabs(a - b) > eps;
    if(select == "<")return a - b < -eps;
    if(select == "<=")return a - b < eps;
    if(select == ">")return a - b > eps;
    if(select == ">=")return a - b > -eps;
}


//--------------------------

const ll mod = 1000000007;
const int maxn = 100010;







int k, m, s, e;
map<int, int> mm;
int cnt = 0;


struct Martix {
    int maps[210][210];

    Martix operator*(const Martix &m)const {
        Martix res;
        memset(res.maps, inf, sizeof(res.maps));
        for(int i = 0; i < cnt; i++) {
            for(int j = 0; j < cnt; j++) {
                for(int k = 0; k < cnt; k++) {
                    res.maps[i][j] = min(maps[i][k] + m.maps[k][j], res.maps[i][j]);
                }
            }
        }
        return res;
    }


    Martix operator^(const ll &b)const {
        ll num = b;
        Martix res;
        Martix tmp  = *this;
        memset(res.maps, inf, sizeof(res.maps));
        for(int i = 0; i < cnt; i++)res.maps[i][i] = 0;
        while(num) {
            if(num & 1)res = res * tmp;
            tmp = tmp * tmp;
            num >>= 1;
        }
        return res;
    }
};




void solve() {
    while(~scanf("%d%d%d%d", &k, &m, &s, &e)) {
        int w, u, v;
        mm.clear();
        Martix A;
        cnt = 0;
        memset(A.maps, inf, sizeof(A.maps));
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &w, &u, &v);
            if(mm.find(u) == mm.end()) {
                mm[u] = cnt++;
            }
            if(mm.find(v) == mm.end()) {
                mm[v] = cnt++;
            }
            A.maps[mm[u]][mm[v]] = w;
            A.maps[mm[v]][mm[u]] = w;
        }

        Martix B = A ^ k;
        // for(int i = 0; i < cnt; i++) {
        //     for(int j = 0; j < cnt; j++) {
        //         printf("%d ", B.maps[i][j] );
        //     }
        //     puts("");
        // }
        printf("%d\n", B.maps[mm[s]][mm[e]]) ;
    }

}

int main() {

#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    // iostream::sync_with_stdio(false);
    solve();
    return 0;
}