450D - Jzzhu and Cities - CodeForces Solution

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m, k, x, y, w, res=0;
    vector<vector<tuple<ll, ll, ll>>> arr(200005);
    vector<ll> cost(200005, -1);
    tuple<ll, ll, ll> h;
    ll node, nodecost;
    bool f=0;
    set<tuple<ll, ll, ll>> st;
    cin>>n>>m>>k;
    while(m--){
        cin>>x>>y>>w;
        arr[x].emplace_back(make_tuple(y, w, 0));
        arr[y].emplace_back(make_tuple(x, w, 0));
    }
    for(ll i=0; i<k; i++){
        cin>>x>>y;
        arr[x].emplace_back(make_tuple(1, y, 1));
        arr[1].emplace_back(make_tuple(x, y, 1));
    }
    st.insert({0, 1, 0});
    while(!st.empty()){
        h=*st.begin();
        st.erase(h);
        node=get<1>(h), nodecost=get<0>(h);
        if(cost[node]!=-1) continue;
        if(get<2>(h)==1) res++;
        cost[node]=nodecost;
        for(auto s : arr[node]){
            if(cost[get<0>(s)]==-1){
                st.insert({nodecost+get<1>(s), get<0>(s), get<2>(s)});
            }
        }

    }
    vector<bool> vis(200005, false);
    cout<<k-res;
    return 0;
}