# @bzoj - [email protected] [POI2015] Wycieczki

input

output

sample input
6 6 11
1 2 1
2 3 2
3 4 2
4 5 1
5 3 1
4 6 3
sample output
4
sample explain

## @[email protected]

$F[k] = G1*F[k-1] + G2*F[k-2] + G3*F[k-3]$

$\begin{bmatrix} 1 & i & o1 & o1\o2 & G1 & G2 & G3\o2 & I & O & O\o2 & O & I & O\\end{bmatrix} \begin{bmatrix} S[k-1]\F[k-1]\F[k-2]\F[k-3]\\end{bmatrix} = \begin{bmatrix} S[k]\F[k]\F[k-1]\F[k-2]\\end{bmatrix}$

## @accepted [email protected]

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 40 + 5;
struct matrix{
long double m[3*MAXN][3*MAXN];
int r, c;
}G[64 + 5];
int n;
long double fun(matrix A) {
long double ret = 0;
for(int i=1;i<=n;i++)
ret += A.m[0][i];
return ret;
}
matrix operator * (matrix A, matrix B) {
matrix C; C.r = A.r, C.c = B.c;
for(int i=0;i<C.r;i++)
for(int j=0;j<C.c;j++) {
C.m[i][j] = 0;
for(int k=0;k<A.c;k++)
C.m[i][j] += A.m[i][k]*B.m[k][j];
}
return C;
}
int main() {
int m; long double k;
scanf("%d%d", &n, &m);
cin >> k; k += n;
G[0].r = G[0].c = 3*n + 1;
for(int i=0;i<=n;i++) G[0].m[0][i]++;
for(int i=1;i<=n;i++) G[0].m[i+n][i]++, G[0].m[i+2*n][i+n]++;
for(int i=1;i<=m;i++) {
int u, v, c; scanf("%d%d%d", &u, &v, &c);
G[0].m[u][v+c*n-n]++;
}
int i;
for(i=1;i<=65;i++) {
G[i] = G[i-1]*G[i-1];
if( fun(G[i]) >= k ) break;
if( i == 65 ) {
puts("-1");
return 0;
}
}
i--;
matrix M = G[i];
long long ret = 1LL<<i;
for(;i>=0;i--) {
if( fun(M*G[i]) < k ) {
ret += (1LL<<i);
M = M*G[i];
}
}
printf("%lld\n", ret);
}

## @[email protected]

@bzoj - [email protected] [POI2015] Wycieczki

(0)
(0)