题解 P6190 【[NOI Online 入门组]魔法（民间数据）】

· · 题解

这题其实考察了一个小\mathrm {trick}。

这个\mathrm {trick}我第一次见到是在做 IOI2020 国家集训队作业的时候看到的，题号是Codeforces 576D

对于一个邻接矩阵G，那么G^k表示的就是恰好经过k后的状态。

举一个比较简单的例子：

**这个其实就代替了做动态规划的必要** 因为这$k$步，每一步的本质相同，只是对应的状态不同，所以我们考虑重载矩阵乘法的定义，了解过动态 DP 的读者也可以类比动态 DP。 对应到这道题，我们首先计算出一步能够得到的状态，然后用相同的转移来做矩阵快速幂即可。 时间复杂度 $O(n^3Log_2 k) 
#define int long long
const int N = 105;
const int M = 2505;
int n, m, kk;
struct Matrix {
  int a[N][N];
  int* operator[](int i) {
    return a[i];
  }
  Matrix operator*(Matrix oth) {
    Matrix res; 
    memset(res.a, 0x3f, sizeof res.a);
    For (k, 0, n - 1) {
      For (i, 0, n - 1) {
        For (j, 0, n - 1) {
          chkmin(res[i][j], a[i][k] + oth[k][j]);
        }
      }
    } 
    return res;
  }
  friend Matrix operator^(Matrix x, int idx) {
    Matrix res = x; 
    idx--;
    for (; idx; idx >>= 1, x = x * x) {
      if (idx & 1) {
        res = res * x;
      }
    }
    return res;
  }
};
struct Path {
  int u, v, t;
} path[M];
int g[N][N];
signed main() {
  memset(g, 0x3f, sizeof g);
  read(n), read(m), read(kk);
  For (i, 0, m - 1) {
    read(path[i].u), read(path[i].v), read(path[i].t);
    path[i].u--, path[i].v--;
    g[path[i].u][path[i].v] = path[i].t;
  }
  For (i, 0, n - 1) {
    g[i][i] = 0;
  }
  For (k, 0, n - 1) {
    For (i, 0, n - 1) {
      For (j, 0, n - 1) {
        chkmin(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
  Matrix base;
  memset(base.a, 0x3f, sizeof base.a);
  For (i, 0, n - 1) {
    base[i][i] = 0;
  }
  For (i, 0, m - 1) {
    int u = path[i].u, v = path[i].v, t = path[i].t;
    For (j, 0, n - 1) {
      For (k, 0, n - 1) {
        chkmin(base[j][k], g[j][u] - t + g[v][k]);
      }
    } 
  }
  if (kk) {
    writeln((base ^ kk)[0][n - 1]);
  } else {
    writeln(g[0][n - 1]);
  }
  return 0;
}