CFR 507 E. Breaking Good ( Dijkstra )
題意:
給一個無向圖,有些邊是壞掉的。求一個 1 走到 N 的最短路徑,使得此路徑壞掉的邊最少,且路徑外沒壞掉的邊最少。
資料規模:
The first line of input contains two integers n, m (2 ≤ n ≤ 1e5, ), the number of cities and number of roads respectively.
In following m lines there are descriptions of roads. Each description consists of three integers x, y, z (1 ≤ x, y ≤ n, ) meaning that there is a road connecting cities number x and y. If z = 1, this road is working, otherwise it is not.
解法:
由於壞掉的邊的數量不變,題意即須在最短路徑前提下有路徑內壞掉的邊最少。
將走一步的邊權設為 N,若當前轉移的這條邊是壞的,權值再加 1。
時間 / 空間複雜度:
O( N lg N ) / O( N )
#include <bits/stdc++.h> using namespace std; template< class T1, class T2 > int upmax( T1 &x, T2 v ){ if( x >= v ) return 0; x = v; return 1; } typedef long long ll; const int MAXN = ( int ) 1e5; int N, M; vector< pair< int, int > > G[ MAXN ]; ll dp[ MAXN ]; int pre[ MAXN ]; signed main(){ ios::sync_with_stdio( 0 ); cin >> N >> M; for( int i = 0; i < M; ++i ){ int u, v, w; cin >> u >> v >> w; --u, --v; G[ u ].emplace_back( w, v ); G[ v ].emplace_back( w, u ); } { for( int i = 0; i < N; ++i ){ dp[ i ] = - ( 1LL << 50 ); pre[ i ] = -1; } priority_queue< pair< ll, int > > pq; pq.emplace( dp[ 0 ] = 0LL, 0 ); while( not pq.empty() ){ ll d; int u; tie( d, u ) = pq.top(); pq.pop(); if( d != dp[ u ] ) continue; d *= -1; for( int i = 0; i < G[ u ].size(); ++i ){ int w, v; tie( w, v ) = G[ u ][ i ]; if( upmax( dp[ v ], - ( d + MAXN + not w ) ) ){ pre[ v ] = u; pq.emplace( dp[ v ], v ); } } } } { set< pair< int, int > > on_path; for( int u = N - 1; u != 0; u = pre[ u ] ){ int x = u; int y = pre[ u ]; if( not ( x < y ) ) swap( x, y ); on_path.emplace( x, y ); } vector< tuple< int, int, int > > ans; for( int i = 0; i < N; ++i ){ for( int j = 0; j < G[ i ].size(); ++j ){ int a = i, b = G[ i ][ j ].second, c = G[ i ][ j ].first; if( not ( a < b ) ) continue; if( on_path.count( make_pair( a, b ) ) ){ if( not c ){ ans.emplace_back( a + 1, b + 1, 1 ); } } else{ if( c ){ ans.emplace_back( a + 1, b + 1, 0 ); } } } } cout << ans.size() << endl; for( int i = 0; i < ans.size(); ++i ){ int a, b, c; tie( a, b, c ) = ans[ i ]; cout << a << " " << b << " " << c << "\n"; } } return 0; }