Codeforces 449B - Jzzhu and Cities

Problem Statement:
449B - Jzzhu and Cities

Solution:
An interesting graph problem. In both Bellman-Ford and Dijkstra single source shortest path algorithms, we have the concept of "relaxed" edges, in which intuitively can be viewed this way: We are given a set of balls connected together with strings. If we choose a ball as the "source" and pick it up, other balls will be hanging with some strings tight and some strings slack. The tight strings are the "relaxed" edges in single source shortest path algorithm. Those which are not relaxed can actually be removed from the shortest path graph.



To solve this problem, we can run Dijkstra algorithm from vertex 1, and in the process of updating shortest paths of other vertices v, we take note of the edge passed leading to v. Furthermore, as far as possible we want to use edges defined by the roads rather than edges defined by the train routes. Eventually the whole strategy will look like a simple extension of Dijkstra algorithm.

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

int N,M,K;
vector<vector<pair<int,int> > > adj;
int par[100005];
long long dist[100005];
long long edge[400005];
int relaxed[400005];

void dijkstra(){
    priority_queue<pair<long long, int> > q;
    for(int i=1;i<=N;++i)dist[i] = (long long) 1e16;
    for(int i=1;i<=N;++i)par[i] = -1;
    dist[1] = 0;
    q.push(make_pair(dist[1],1));
    while(!q.empty()){
        long long d = -q.top().first;
        int u = q.top().second;
        q.pop();
        if(d > dist[u])continue;
        for(int i=0;i<adj[u].size();++i){
            int v = adj[u][i].first;
            int e = adj[u][i].second;
            if(dist[v] > d + edge[e]){
                dist[v] = d + edge[e];
                par[v] = e;
                q.push(make_pair(-dist[v],v));
            } else if(dist[v] == d + edge[e]){
                if(e < M){
                    par[v] = e;
                }
            }
        }
    }
}

int main(){
    int u,v;
    long long w;
    scanf("%d%d%d",&N,&M,&K);
    adj = vector<vector<pair<int,int> > > (N+3);
    for(int i=0;i<M;++i){
        scanf("%d%d%I64d",&u,&v,&w);
        adj[u].push_back(make_pair(v,i));
        adj[v].push_back(make_pair(u,i));
        edge[i] = w;
    }
    for(int i=0;i<K;++i){
        scanf("%d%I64d",&v,&w);
        adj[1].push_back(make_pair(v,i+M));
        adj[v].push_back(make_pair(1,i+M));
        edge[i+M] = w;
    }
    dijkstra();
    for(int i=1;i<=N;++i){
        if(par[i]==-1)continue;
        relaxed[par[i]] = 1;
    }
    int ans = 0;
    for(int i=M;i<M+K;++i){
        if(!relaxed[i]) ++ans;
    }
    printf("%d\n",ans);
    return 0;
}