Codeforces Round #287 Problem E - Breaking Good

Problem Statement:
507E - Breaking Good

Solution:
[Off topic: btw, Breaking Bad is damn awesome!]
This problem employs an interesting trick using Dijkstra Algorithm, which is quite intuitive to discover.

First suppose there are no broken roads, i.e. every edges are valid edges. In this case, we can simply run a BFS to find the shortest path between node 1 (city) and node N (headquarter), and for all other roads not in this path, we just blow them up. However, in the problem, we can have roads which must be repaired before it can be used. Hence naturally BFS is not applicable to this case anymore and we need something else to account for the cost of repairing a road. Yet, we also need the property that the shortest path will still have the same length as the ones that are produced if we are to run BFS.



Hence the Dijkstra trick. For each broken roads, we can define the cost of passing this road as 1, and similarly for roads that are not broken as 0. Hence if we run Dijkstra, it will find roads with as little broken roads as possible. However this does not guarantee that the length of the path is the shortest. To do so, in addition to the total cost already incurred, in each iteration of the algorithm, we also keep track on the number of edges already traversed to reach the current node. This depth will also serve as an additional penalty to the cost so far incurred, hence with suitable cost function, would lead to the algorithm to prefer choosing a broken road if it leads to building the shortest path. I think there can be several different implementation of the idea, and here is one:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
#include <cassert>
using namespace std;

// WRONG IDEA

long long INF = (long long) 1e18;

long long dist[100005];
int par[100005];
int path[100005];
int edges[100005][2];
int ok[100005];
long long weight[100005];
int mark[100005];
vector<vector<pair<long long,int> > > adj;
int N, M;
int S = 1, T;
void dijkstra() {
    priority_queue<pair<long long,pair<int,int> > > pq;
    for(int i=0;i<=N;++i){
        par[i] = -1;
        dist[i] = INF;
    }
    dist[S] = 0;
    pq.push(make_pair(0, make_pair(0, S)));
    while(!pq.empty()){
        int u = pq.top().second.second;
        long long depth = pq.top().second.first;
        long long d = -pq.top().first;
        pq.pop();
        if(u == T) return;
        if(d != dist[u]) continue;
        for(int i=0;i<adj[u].size();++i){
            int v = adj[u][i].first;
            long long w = weight[adj[u][i].second];
            if(w + d + 1LL * 100001 * depth < dist[v]) {
                dist[v] = w+d+1LL*100001*depth;
                pq.push(make_pair(-dist[v], make_pair(depth+1, v)));
                par[v] = u;
                path[v] = adj[u][i].second;
            }
        }
    }
}

int main(){
    int x,y,z;
    scanf("%d%d",&N,&M);
    T=N;
    adj = vector<vector<pair<long long,int> > > (N+3);
    for(int i=0;i<M;++i){
        scanf("%d%d%d",&x,&y,&z);
        adj[x].push_back(make_pair(y, i));
        adj[y].push_back(make_pair(x, i));
        edges[i][0] = x;
        edges[i][1] = y;
        ok[i] = z;
        weight[i] = (ok[i] ? 0 : 1);
    }
    dijkstra();
    int cur = T;
    vector<pair<pair<int,int>,int> > st;
    while(cur != 1) {
        assert(cur != -1);
        mark[path[cur]] = 1;
        if(ok[path[cur]] == 0) {
            st.push_back(make_pair(make_pair(edges[path[cur]][0], edges[path[cur]][1]), 1));
        }
        cur = par[cur];
    }
    for(int i=0;i<M;++i){
        if(mark[i])continue;
        if(ok[i]) st.push_back(make_pair(make_pair(edges[i][0], edges[i][1]),0));
    }
    printf("%d\n",(int)st.size());
    for(int i=0;i<st.size();++i){
        printf("%d %d %d\n", st[i].first.first, st[i].first.second, st[i].second);
    }
    return 0;
}