Code : Jzzhu and Cities

#include <bits/stdc++.h>
using namespace std;

const long long inf = (long long)1e12;

class Graph {
  public:
    int n;
    vector<vector<pair<int, long long>>> adj;
    Graph(int n) {
        this->n = n;
        adj.resize(n);
    }

  public:
    void dijkstra(vector<int> &s, vector<int> &y);
};

void Graph ::dijkstra(vector<int> &s, vector<int> &y) {
    int src = 0;
    vector<long long> d(n, inf);

    // black_index[i] = j means that the you used the j-th black wave to get
    // the shortest path to this vertex.
    // If j = -1, it means that the vertex can be visited using only white
    // waves.
    vector<int> black_index(n, -1);

    // heap contains (dist, black_index, ind)
    set<pair<long long, pair<int, int>>> heap;

    auto add = [&](int i) { heap.insert({d[i], {black_index[i], i}}); };
    auto remove = [&](int i) { heap.erase({d[i], {black_index[i], i}}); };

    d[src] = 0;
    black_index[src] = -1;
    for (int i = 0; i < n; i++) {
        add(i);
    }

    for (int i = 0; i < (int)s.size(); i++) {
        int v = s[i];
        if (d[v] > y[i]) {
            remove(v);
            d[v] = y[i];
            black_index[v] = i;
            add(v);
        }
    }

    for (int i = 0; i < n; i++) {
        int v = heap.begin()->second.second;
        heap.erase(heap.begin());

        for (auto [c, w] : adj[v]) {
            auto nxt = d[v] + w;
            if (d[c] > nxt) {
                remove(c);
                d[c] = nxt;
                black_index[c] = black_index[v];
                add(c);
            } else if (d[c] == nxt && black_index[c] != -1) {
                remove(c);
                black_index[c] = black_index[v];
                add(c);
            }
        }
    }

    set<int> dist;
    for (int i = 0; i < n; i++) {
        if (black_index[i] != -1) {
            dist.insert(black_index[i]);
        }
    }
    cout << (int)s.size() - (int)dist.size() << endl;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--;
        y--;
        g.adj[x].push_back({y, w});
        g.adj[y].push_back({x, w});
    }

    vector<int> s(k), y(k);
    for (int i = 0; i < k; i++) {
        cin >> s[i] >> y[i];
        s[i]--;
    }

    g.dijkstra(s, y);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const long long inf = (long long)1e12;

class Graph {
  public:
    int n;
    vector<vector<pair<int, long long>>> adj;
    Graph(int n) {
        this->n = n;
        adj.resize(n);
    }

  public:
    void dijkstra(vector<int> &s, vector<int> &y);
};

void Graph ::dijkstra(vector<int> &s, vector<int> &y) {
    int src = 0;
    vector<long long> d(n, inf);

    // black_index[i] = j means that the you used the j-th black wave to get
    // the shortest path to this vertex.
    // If j = -1, it means that the vertex can be visited using only white
    // waves.
    vector<int> black_index(n, -1);

    // heap contains (dist, black_index, ind)
    set<pair<long long, pair<int, int>>> heap;

    d[src] = 0;
    black_index[src] = -1;
    for (int i = 0; i < n; i++) {
        heap.insert({d[i], {black_index[i], i}});
    }

    for (int i = 0; i < (int)s.size(); i++) {
        int v = s[i];
        if (d[v] > y[i]) {
            heap.erase({d[v], {black_index[v], v}});
            d[v] = y[i];
            black_index[v] = i;
            heap.insert({d[v], {black_index[v], v}});
        }
    }

    for (int i = 0; i < n; i++) {
        int v = heap.begin()->second.second;
        heap.erase(heap.begin());

        for (auto [c, w] : adj[v]) {
            auto nxt = d[v] + w;
            if (d[c] > nxt) {
                heap.erase({d[c], {black_index[c], c}});
                d[c] = nxt;
                black_index[c] = black_index[v];
                heap.insert({d[c], {black_index[c], c}});
            } else if (d[c] == nxt && black_index[c] != -1) {
                heap.erase({d[c], {black_index[c], c}});
                black_index[c] = black_index[v];
                heap.insert({d[c], {black_index[c], c}});
            }
        }
    }

    set<int> dist;
    for (int i = 0; i < n; i++) {
        if (black_index[i] != -1) {
            dist.insert(black_index[i]);
        }
    }
    cout << (int)s.size() - (int)dist.size() << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--;
        y--;
        g.adj[x].push_back({y, w});
        g.adj[y].push_back({x, w});
    }

    vector<int> s(k), y(k);
    for (int i = 0; i < k; i++) {
        cin >> s[i] >> y[i];
        s[i]--;
    }

    g.dijkstra(s, y);
}

int main() {
    solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const long long inf = (long long)1e12;

class Graph {
  public:
    int n;
    vector<vector<pair<int, long long>>> adj;
    Graph(int n) {
        this->n = n;
        adj.resize(n);
    }

  public:
    void dijkstra(vector<int> &s, vector<int> &y);
};

void Graph ::dijkstra(vector<int> &s, vector<int> &y) {
    int src = 0;
    vector<long long> wave_arrival_time(n, inf);
    vector<bool> visited(n);

    // black_index[i] = j means that the you used the j-th black wave to get
    // the shortest path to this vertex.
    // If j = -1, it means that the vertex can be visited using only white
    // waves.
    vector<int> black_index(n, -1);

    wave_arrival_time[src] = 0;
    black_index[src] = -1;

    for (int i = 0; i < (int)s.size(); i++) {
        if (wave_arrival_time[s[i]] > y[i]) {
            wave_arrival_time[s[i]] = y[i];
            black_index[s[i]] = i;
        }
    }

    // At every minute, a wave reaches a vertex for the first time, and
    // that timestamp is the shortest path of that node from src.
    // Hence, we only need to run this algorithm for n times.
    for (int i = 0; i < n; i++) {
        int vertex;
        long long current_time = inf;
        for (int v = 0; v < n; v++) {
            // If 2 waves arrive at the same time, prefer the white wave.
            if (!visited[v] && wave_arrival_time[v] < current_time) {
                current_time = wave_arrival_time[v];
                vertex = v;
            } else if (!visited[v] && wave_arrival_time[v] == current_time &&
                       black_index[v] == -1) {
                vertex = v;
            }
        }

        visited[vertex] = true;

        // Emit waves for all the neighbors.
        for (auto [child, w] : adj[vertex]) {
            auto arrival_time_of_this_wave = current_time + w;
            // Ignore the wave if there's a faster wave that would arrive
            // at the children.
            if (wave_arrival_time[child] > arrival_time_of_this_wave) {
                wave_arrival_time[child] = arrival_time_of_this_wave;
                black_index[child] = black_index[vertex];
            } else if (wave_arrival_time[child] == arrival_time_of_this_wave &&
                       black_index[child] != -1) {
                black_index[child] = black_index[vertex];
            }
        }
    }

    set<int> dist;
    for (int i = 0; i < n; i++) {
        if (black_index[i] != -1) {
            dist.insert(black_index[i]);
        }
    }
    cout << (int)s.size() - (int)dist.size() << endl;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--;
        y--;
        g.adj[x].push_back({y, w});
        g.adj[y].push_back({x, w});
    }

    vector<int> s(k), y(k);
    for (int i = 0; i < k; i++) {
        cin >> s[i] >> y[i];
        s[i]--;
    }

    g.dijkstra(s, y);
}

int main() {
    solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const long long inf = (long long)1e12;

class Graph {
  public:
    int n;
    vector<vector<pair<int, long long>>> adj;
    Graph(int n) {
        this->n = n;
        adj.resize(n);
    }

  public:
    void dijkstra(vector<int> &s, vector<int> &y);
};

void Graph ::dijkstra(vector<int> &s, vector<int> &y) {
    int src = 0;
    vector<long long> wave_arrival_time(n, inf);
    vector<bool> visited(n);

    // black_index[i] = j means that the you used the j-th black wave to get
    // the shortest path to this vertex.
    // If j = -1, it means that the vertex can be visited using only white
    // waves.
    vector<int> black_index(n, -1);

    wave_arrival_time[src] = 0;
    black_index[src] = -1;

    for (int i = 0; i < (int)s.size(); i++) {
        if (wave_arrival_time[s[i]] > y[i]) {
            wave_arrival_time[s[i]] = y[i];
            black_index[s[i]] = i;
        }
    }

    // At every minute, a wave reaches a vertex for the first time, and
    // that timestamp is the shortest path of that node from src.
    // Hence, we only need to run this algorithm for n times.
    for (int i = 0; i < n; i++) {
        int vertex;
        long long current_time = inf;
        for (int v = 0; v < n; v++) {
            // If 2 waves arrive at the same time, prefer the white wave.
            if (!visited[v] && wave_arrival_time[v] < current_time) {
                current_time = wave_arrival_time[v];
                vertex = v;
            } else if (!visited[v] && wave_arrival_time[v] == current_time &&
                       black_index[v] == -1) {
                vertex = v;
            }
        }

        visited[vertex] = true;

        // Emit waves for all the neighbors.
        for (auto [child, w] : adj[vertex]) {
            auto arrival_time_of_this_wave = current_time + w;
            // Ignore the wave if there's a faster wave that would arrive
            // at the children.
            if (wave_arrival_time[child] > arrival_time_of_this_wave) {
                wave_arrival_time[child] = arrival_time_of_this_wave;
                black_index[child] = black_index[vertex];
            } else if (wave_arrival_time[child] == arrival_time_of_this_wave &&
                       black_index[vertex] == -1) {
                black_index[child] = -1;
            }
        }
    }

    set<int> dist;
    for (int i = 0; i < n; i++) {
        if (black_index[i] != -1) {
            dist.insert(black_index[i]);
        }
    }

    cout << (int)s.size() - (int)dist.size() << endl;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--;
        y--;
        g.adj[x].push_back({y, w});
        g.adj[y].push_back({x, w});
    }

    vector<int> s(k), y(k);
    for (int i = 0; i < k; i++) {
        cin >> s[i] >> y[i];
        s[i]--;
    }

    g.dijkstra(s, y);
}

int main() {
    solve();
    return 0;
}