# CFR 147 B. Smile House ( Binary Search, Fast Matrix Multiplication, DP, Binary Enumeration )

Problem - B - Codeforces

dp[ i ][ j ][ k ] : 經過 i 個邊後，j 至 k 的最大可能距離

dp[ i ][ j ][ k ] = max{ dp[ i - 1 ][ j ][ x ] + dp[ 1 ][ x ][ k ] | j != x and x != k }

O( N ^ 3 lg N )

Before:

```int N, M;
vvi edge;

void init(){
cin >> N >> M;
edge = vvi( N, vi( N, -INF ) );
for( int i = 0; i < N; ++i )
edge[ i ][ i ] = 0;
for( int i = 0; i < M; ++i ){
int u, v, wgo, wback;
cin >> u >> v >> wgo >> wback;
--u, --v;
edge[ u ][ v ] = wgo;
edge[ v ][ u ] = wback;
}
}

vvi mat_mul( vvi a, vvi b ){
vvi res( a.size(), vi( b[ 0 ].size(), -INF ) );
for( int i = 0; i < a.size(); ++i )
for( int j = 0; j < a[ 0 ].size(); ++j )
for( int k = 0; k < b[ 0 ].size(); ++k ) if( a[ i ][ j ] != -INF and b[ j ][ k ] != -INF )
upmax( res[ i ][ k ], a[ i ][ j ] + b[ j ][ k ] );
return res;
}

vvi mat_pow( vvi a, int p ){
vvi res( a.size(), vi( a.size(), -INF ) );
for( int i = 0; i < a.size(); ++i )
res[ i ][ i ] = 0;
while( p ){
if( p & 1 )
res = mat_mul( res, a );
p >>= 1, a = mat_mul( a, a );
}
return res;
}

void solve(){
int ans = 0;
int lb = 1, rb = N;
while( lb <= rb ){
int mid = lb + rb >> 1;
vvi x = mat_pow( edge, mid );
int ok = 0;
for( int i = 0; i < N; ++i )
ok |= x[ i ][ i ] > 0;
if( ok )
ans = mid, rb = mid - 1;
else
lb = mid + 1;
}
cout << ans << endl;
}
```

After:

```typedef tuple< int, int, int, int > t4i;

int N, M;
vector< t4i > C;

void init(){
cin >> N >> M;
C = vector< t4i >( M );
for( int i = 0; i < M; ++i ){
int x, y, cxy, cyx;
cin >> x >> y >> cxy >> cyx;
C[ i ] = make_tuple( x - 1, y - 1, cxy, cyx );
}
}

int maxp;
vvvi dbl; // doubled path matrix : shortest path matrix for 2 ^ i number of edges path only
vvvi pdbl; // dot product of first i doubled path matrices

vvi I; // identity matrix

vvi mat_mul( vvi a, vvi b ){
vvi res = I;
for( int i = 0; i < a.size(); ++i )
for( int j = 0; j < b.size(); ++j )
for( int k = 0; k < b[ 0 ].size(); ++k )
upmax( res[ i ][ k ], a[ i ][ j ] + b[ j ][ k ] );
return res;
}

void preprocess(){
I = vvi( N, vi( N, -INF ) );
for( int i = 0; i < N; ++i )
I[ i ][ i ] = 0;
maxp = 32 - __builtin_clz( N )  - 1;
dbl = pdbl = vvvi( maxp + 1, vvi( N, vi( N ) ) );
dbl[ 0 ] = I;
for( int i = 0; i < M; ++i ){
int x, y, cxy, cyx;
tie( x, y, cxy, cyx ) = C[ i ];
dbl[ 0 ][ x ][ y ] = cxy;
dbl[ 0 ][ y ][ x ] = cyx;
}
for( int i = 0; i < maxp; ++i )
dbl[ i + 1 ] = mat_mul( dbl[ i ], dbl[ i ] );
pdbl[ 0 ] = I;
for( int i = 0; i < maxp; ++i )
pdbl[ i + 1 ] = mat_mul( pdbl[ i ], dbl[ i ] );
}

void solve(){
int ans = 0;
vvi pre = I;
for( int i = maxp; 0 <= i; --i ){
int ok = 0;
vvi cur = mat_mul( pre, pdbl[ i ] );
for( int j = 0; j < N; ++j )
ok |= cur[ j ][ j ] > 0;
if( not ok )
ans |= 1 << i,
pre = mat_mul( pre, dbl[ i ] );
}
int ok = 0;
for( int i = 0; i < N; ++i )
ok |= pre[ i ][ i ] > 0;
if( not ok )
cout << 0 << endl;
else
cout << ans << endl;
}
```