1120考试T2
题目大意:
给你一个n个点，m条边的图，每条边有一个权值在某几个时刻有一些点不能走，每次必须走一条边，求恰好k时刻到达终点的路径中最大边权最小.
其中不能走的点是这样的: 有\(num\)个机器人, 每个机器人会周期性的按顺序走一些点, 编号为\(t_1, t_2, ...\)
\(n <= 50, m <= 1600, k <= 1e8, num <= 10, t_i <= 4\)
矩阵快速幂.
我们发现\(t\)最大只有4, 得出这些机器人最多只会有12种所在点的状态, 也就是12个一循环.
那么我们可以处理出这12个矩阵, 也就是在这些状态下那些点不能走, 然后把这12个矩阵相乘, 就得到了一次循环后, 各点之间路径的最大边权最小值.
然后我们把这个乘后的矩阵作为转移矩阵, 用矩阵快速幂, 那么指数就应该是\(k / 12\).
对于剩下的\(k \% 12\)次暴力乘就好了.
复杂度\(O(n^2log \ k)\)
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 55, inf = 1e9;
int n, m, k, s, t, num;
int a[N], now[N], dis[N][N], num_a[N];
struct mat {
int v[N][N];
void init() { for(int i = 1;i <= n; i++) for(int j = 1;j <= n; j++) v[i][j] = inf; }
void with_dis() { for(int i = 1;i <= n; i++) for(int j = 1;j <= n; j++) v[i][j] = dis[i][j]; }
} ans, turn, q[13];
mat operator * (const mat &a, const mat &b) {
mat c; c.init();
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
for(int k = 1;k <= n; k++)
if(a.v[i][k]) c.v[i][j] = min(c.v[i][j], max(a.v[i][k], b.v[k][j]));
return c;
}
mat ksm(mat x, int y) {
mat res; res.init();
for(int i = 1;i <= n; i++) res.v[i][i] = 1;
while(y) { if(y & 1) res = res * x; x = x * x; y >>= 1; }
return res;
}
int main() {
n = read(); m = read(); k = read();
if(m == 0 && k == 0) { printf("0"); return 0; }
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++) dis[i][j] = inf;
for(int i = 1, x, y, z;i <= m; i++) {
x = read(); y = read(); z = read();
if(dis[x][y]) dis[x][y] = dis[y][x] = min(dis[x][y], z);
else dis[x][y] = dis[y][x] = z;
}
for(int i = 1;i <= 12; i++) q[i].with_dis();
num = read(); s = read(); t = read(); ans.init();
for(int i = 1, x;i <= num; i++) {
x = read();
for(int j = 1;j <= x; j++) a[j] = read();
for(int j = 1;j <= 12; j++) {
int p = a[j % x == 0 ? x : j % x];
for(int l = 1;l <= n; l++) q[j].v[l][p] = inf;
}
}
turn = q[1];
for(int i = 2;i <= 12; i++) turn = turn * q[i];
ans = ksm(turn, k / 12);
for(int i = 1;i <= k % 12; i++) ans = ans * q[i];
if(ans.v[s][t] == 1e9) printf("impossible");
else printf("%d", ans.v[s][t]);
return 0;
}