拆点， 矩阵乘法，路径计数。

Table of Contents

  1. Description
  2. Solution

Description

给定一张n个点m条边的带权有向图，每条边的边权只可能是1，2，3中的一种。

将所有可能的路径按路径长度排序，请输出第k小的路径的长度，注意路径不一定是简单路径，即可以重复走同一个点。

Solution

看到巨大的数据范围就会想到log级别的算法了，此题点数不多，矩阵乘法是一个选择。

实际操作可以类比一道边权在10以内的题，我们也可以按单位距离拆点，然后进行路径计数，恰好等于K时走了多少步，就是答案长度了。

写起来有很多细节，而且计数很容易爆long long，膜了GXZLegend的题解，可以绑一个计数器到各个点，然后用倍增的方式，逐次累加答案并构造出答案的每个二进制位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
 
using namespace std;
 
const int maxp = 121;
const int maxn = 41;
 
typedef long long ll;
 
int n, m, lim;
ll k, ans;
 
struct matrix
{
  ll val[maxp][maxp];
  matrix() {
    memset(val, 0, sizeof val);
  }
  ll& operator () (int x, int y) {
    return val[x][y];
  }
  matrix operator * (matrix b) {
    matrix ret;
    for (int k = 0; k <= lim; ++k)
      for (int i = 0; i <= lim; ++i)
        for (int j = 0; j <= lim; ++j)
          ret(i, j) += val[i][k] * b(k, j);
    return ret;
  }
  bool check() {
    ll count = 0;
    for (int i = 1; i <= n; ++i) {
      count += (val[i][0] - 1);
      if (count >= k) return 1; 
    }
    return 0;
  }
}dou[70], res;
 
int main() {
  int u, v, w;
  scanf("%d%d%lld", &n, &m, &k);
  dou[0](0,0) = 1; lim = 3 * n;
  for (int i = 1; i <= n; ++i)
    res(i, i) = dou[0](i, 0) = dou[0](i, i + n) = dou[0](i + n, i + 2 * n) = 1;
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    dou[0](u + (w - 1) * n, v)++;
  }
  int tim = 1;
  for(; ; ++tim) {
    if (tim > 65) {
      puts("-1");
      return 0;
    }
    dou[tim] = dou[tim - 1] * dou[tim - 1];
    if (dou[tim].check()) break;
  }
  tim -= 1;
  for (; tim >= 0; --tim) {
    matrix tmp = res * dou[tim];
    if (!tmp.check()) res = tmp, ans |= (1ll << tim);
  }
  printf("%lld\n", ans);
  return 0;
}