CFR 257 1B. Jzzhu and Cities ( Dijkstra )

Problem - B - Codeforces
kmjpさんの解法を参考にしました。
kmjp.hatenablog.jp
trainのルートを全部あらかじめpqに入れて、もし一直線で着く方が速いならそれが先に出されて、その場でdisを更新しつつcountを上げる、そうでなければ普通にdijkstraする。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 3e5 + 5;
const int MAXK = 1e5 + 5;
const int MAXX = 1e9 + 9;
const int MAXY = 1e9 + 9;
typedef long long ll;
typedef pair< ll, int > pli;

int n, m, k;

struct Edge{
    int u, v, w;
    Edge( int _u = -1, int _v = -1, int _w = -1 ): u(_u), v(_v), w(_w){}
} road[ MAXM << 1 ], train[ MAXK ];

vector< int > G[ MAXN ]; // will not include train
ll dis[ MAXN ];
int dijk_vis[ MAXN ];

void solve(){
    int used_train_cnt = 0;
    priority_queue< pli, vector< pli >, greater< pli > > pq;
    fill( dis, dis + MAXN, 1LL << 60 );
    for( int i = 0; i < k; ++i ){
        int v = train[ i ].v;
        int w = train[ i ].w;
        pq.push( pli( w, v ) );
    }
    pq.push( pli( dis[ 1 ] = 0, 1 ) );
    while( !pq.empty() ){
        int u = pq.top().second;
        ll w = pq.top().first;
        pq.pop();
        if( dijk_vis[ u ] ) continue;
        dijk_vis[ u ] = 1;
        if( dis[ u ] > w ){
            ++used_train_cnt;
            dis[ u ] = w;
        }
        for( int vidx : G[ u ] ){
            int v = road[ vidx ].v;
            int w = road[ vidx ].w;
            if( dis[ v ] > dis[ u ] + w )
                dis[ v ] = dis[ u ] + w,
                pq.push( pli( dis[ v ], v ) );
        }
    }
    printf("%d\n", k - used_train_cnt);
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for( int i = 0; i < m; ++i ){
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        road[ i ] = Edge( u, v, w );
        G[ u ].push_back( i );
        road[ m + i ] = Edge( v, u, w );
        G[ v ].push_back( m + i );
    }
    for( int i = 0; i < k; ++i ){
        int s, w; scanf("%d%d", &s, &w);
        train[ i ] = Edge( 1, s, w );
    }
    solve();
    return 0;
}