题目描述
给定一张n个点m条边的带权有向图，每条边的边权只可能是1，2，3中的一种。将所有可能的路径按路径长度排序，请输出第k小的路径的长度，注意路径不一定是简单路径，即可以重复走同一个点。
输入输出格式
输入格式：
第一行包含三个整数n,m,k(1<=n<=40，1<=m<=1000，1<=k<=10^18)。接下来m行，每行三个整数u,v,c(1<=u,v<=n，u不等于v，1<=c<=3)，表示从u出发有一条到v的单向边，边长为c。可能有重边。
输出格式：
包含一行一个正整数，即第k短的路径的长度，如果不存在，输出-1。
输入输出样例
输入样例#1：
6 6 11
1 2 1
2 3 2
3 4 2
4 5 1
5 3 1
4 6 3
输出样例#1：
4
说明
给定一张n个点m条边的带权有向图，每条边的边权只可能是1，2，3中的一种。
将所有可能的路径按路径长度排序，请输出第k小的路径的长度，注意路径不一定是简单路径，即可以重复走同一个点。
题解
矩乘(倍增?)
如果边权都是1,把每个点都连向计数点
然后对矩阵做k次快速幂就表示路径长度<=k的路径条数
边权很小一看就可以想到拆点(([SCOI2009])迷路)
对于每个点 , 拆成三个点
第一个点是实点
后两个点是虚点
因为每次转移都只能转移一步表示走一步,这一步长度为1
所以拆点后对于((u,v,w))就相当于转移(w)次才能通过这条路径从(u->v)
然后再把每个实点和计数点((n*3+1))连一条边方便计数
由于一条路径长度不一定等于转移次数
所以再让计数器形成一个自环
这样转移t次后统计计数器的答案表示的就是路径长度<=t的路径条数
然后如果二分路径长度然后(check)的话会T
所以用类似于倍增的方法
预处理出这个矩阵转移(2^i)次后的矩阵
每次处理(2^i)的矩阵完成后(check)一下,如果大于k个就可以停止了
然后再倍增求答案
从大往小里枚举
像倍增跳LCA那样,每当蹦到一个总路径条数<k的状态,就把当前状态更新成那个状态,并加上相应的答案
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
# define int long long
const int M = 125 ;
const int N = 70 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x * w ;
}
int n , m , E , kth , Ans ;
struct Matrix {
int f[M][M] ;
inline Matrix () { memset(f , 0 , sizeof(f)) ; }
inline void Start() { for(int i = 1 ; i <= E ; i ++) f[i][i] = 1 ; }
inline friend Matrix operator * (Matrix a , Matrix b) {
Matrix temp ;
for(int i = 1 ; i <= E ; i ++)
for(int j = 1 ; j <= E ; j ++)
for(int k = 1 ; k <= E ; k ++)
temp.f[i][j] = (temp.f[i][j] + a.f[i][k] * b.f[k][j]) ;
return temp ;
}
inline bool chk() {
int ret = 0 ;
for(int i = 1 ; i <= n ; i ++) {
ret = (ret + f[i][E] - 1) ;
if(ret >= kth || ret < 0)
return true ;
}
return false ;
}
} st[N] , Now , Temp ;
# undef int
int main() {
# define int long long
n = read() ; m = read() ; kth = read() ; E = n * 3 + 1 ; st[0].f[E][E] = 1 ;
for(int i = 1 ; i <= n ; i ++) st[0].f[i][E] = st[0].f[i][i + n] = st[0].f[i + n][i + n * 2] = 1 ;
for(int i = 1 , u , v , w ; i <= m ; i ++) {
u = read() , v = read() , w = read() ;
st[0].f[u + (w - 1) * n][v] ++ ;
}
int Maxup ;
for(int i = 1 ; i <= 63 ; i ++) {
if(i == 63) { printf("-1
") ; return 0 ; }
st[i] = st[i - 1] * st[i - 1] ;
if(st[i].chk()) { Maxup = i ; break ; }
}
Now.Start() ;
for(int i = Maxup ; i >= 0 ; i --) {
Temp = Now * st[i] ;
if(Temp.chk()) continue ;
Now = Temp ; Ans += (1LL << i) ;
}
cout << Ans << endl ;
return 0 ;
}