题目描述

blablabla

样例

blablabla

#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>

using namespace std;

const int N = 110;

int g[N][N], res[N][N];
map<int, int> id;
int idx;
int m, n, S, E;

void mul(int a[][N],int b[][N])
{
    int temp[N][N];
    memset(temp, 0x3f, sizeof temp);

    for(int k = 1;k <= idx;k ++)
        for(int i = 1;i <= idx;i ++)
            for(int j = 1;j <= idx;j ++)
                temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);

    memcpy(a, temp, sizeof temp);
}

void qmi(int x)
{
    memset(res, 0x3f, sizeof res);
    for(int i = 1;i < N;i ++) res[i][i] = 0;

    while(x)
    {
        if(x & 1) mul(res, g);
        mul(g, g);
        x>>=1;
    }
}

int main()
{
    cin>>n>>m>>S>>E;
    memset(g, 0x3f,sizeof g);

    id[S] = ++idx;
    id[E] = ++idx;
    for(int i = 1;i <= m;i ++)
    {
        int a, b, c;
        cin>>c>>a>>b;
        if(!id.count(a)) id[a] = ++idx;
        if(!id.count(b)) id[b] = ++idx;
        a = id[a], b = id[b];
        g[a][b] = min(g[a][b], c);
        g[b][a] = g[a][b];
    }

    qmi(n);

    cout<<res[id[S]][id[E]]<<endl;
}