0w1

CFR 507 E. Breaking Good ( Dijkstra )

Problem - E - Codeforces

題意:
給一個無向圖,有些邊是壞掉的。求一個 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;
}