CodeForces 449B

cf.449B.cpp

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

#define ff(i, n) for (int i = 0, END = (n); i < END; i ++)
#define fff(i, n, m) for (int i = (n), END = (m); i <= END; i ++)
#define dff(i, n, m) for (int i = (n), END = (m); i >= END; i --)
#define travel(e, first) for (int e = first, v = vv[first]; ~e; e = nxt[e], v = vv[e])
#define clr(a, b) memset(a, b, sizeof(a))
typedef long long ll;

int n, m, k;
const int N = 1E5 + 5;
int first[N], vv[8 * N], ww[8 * N], nxt[8 * N], e = 2;
bool road[8 * N];
ll dis[N][2];

void add_edge(int u, int v, int w, bool is_road) {
    nxt[e] = first[u], vv[e] = v, ww[e] = w, road[e] = is_road, first[u] = e ++;
}

int input() {
    clr(first, -1); e = 2;
    clr(dis, -1);

    ff(i, m) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w, true);
        add_edge(v, u, w, true);
    }

    int remove = 0;
    ff(i, k) {
        int v, w;
        scanf("%d%d", &v, &w);

        if (dis[v][0] == -1) {
            dis[v][0] = w;
        } else {
            dis[v][0] = min(dis[v][0], ll(w));
            remove ++;
        }
    }

    fff (v, 2, n) if (~dis[v][0]) {
        ll w = dis[v][0];
        add_edge(1, v, w, false);
        add_edge(v, 1, w, false);
        dis[v][0] = -1;
    }

    return remove;
}

struct Node {
    int u;
    ll d;
    bool r;

    bool operator< (const Node & b) const {
        return d > b.d;
    }
};

void dijkstra() {
    priority_queue<Node> que;
    que.push({1, 0, 0});
    dis[1][1] = 0;

    while (!que.empty()) {
        Node now = que.top(); que.pop();

        int u = now.u;
        ll d = now.d;
        bool r = now.r;

        if (~dis[u][r]) continue;
        dis[u][r] = d;

        travel(e, first[u]) if (dis[v][r || road[e]] == -1) {
            que.push({v, d + ww[e], r || road[e]});
        }
    }
}

int main() {
    while (scanf("%d%d%d", &n, &m, &k) == 3) {
        int ans = input();
        dijkstra();

        fff(i, 2, n) if (~dis[i][1] && dis[i][0] >= dis[i][1]) {
            ans ++;
        }
        printf("%d\n", ans);
    }
}