牛站

AcWing-345-牛站

分析

见《进阶指南》第362页。

实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 210, M = 110;
struct edge {
    int u, v, w;
};
int n, m, s, t;
edge e[M];
int tot, nums[N];
struct matrix {
    static int n;
    int m[N][N];

    matrix () {
        memset(m, 0x3f, sizeof(m));
    }
    friend matrix operator * (const matrix& a, const matrix& b) { // 广义矩阵乘法
        matrix res;
        for (int i = 1; i <= n; ++ i)
            for (int k = 1; k <= n; ++ k)
                for (int j = 1; j <= n; ++ j)
                    res.m[i][j] = min(res.m[i][j], a.m[i][k] + b.m[k][j]);
        return res;
    }
    friend matrix operator ^ (matrix a, int b) {
        matrix res = a;
        b = b - 1; // 技巧
        while (b > 0) {
            if (b & 1) res = res * a;
            a = a * a;
            b /= 2;
        }
        return res;
    }
};
int matrix::n = 0;

void discrete () {
    for (int i = 1; i <= m; ++ i) {
        nums[i] = e[i].u;
        nums[m + i] = e[i].v;
    }
    sort(nums + 1, nums + 2 * m + 1);
    tot = unique(nums + 1, nums + 2 * m + 1) - (nums + 1);
}
int query (int x) {
    return lower_bound(nums + 1, nums + tot + 1, x) - nums;
}

int main () {
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; ++ i)
        cin >> e[i].w >> e[i].u >> e[i].v;

    discrete();
    for (int i = 1; i <= m; ++ i) {
        e[i].u = query(e[i].u);
        e[i].v = query(e[i].v);
    }

    matrix::n = tot;
    matrix A;
    for (int i = 1; i <= m; ++ i) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        A.m[u][v] = A.m[v][u] = w;
    }
    cout << (A^n).m[query(s)][query(t)] << endl;
    return 0;
}