結果

提出番号	1717
提出者	nxteru
言語	C++
提出日時	2018-08-04 13:36:48
問題名	(73)観光計画
結果	AC
点数	100%

---

テストケース

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
int n,m,k;
vector<P>g[100005];
ll d[100005];
int main(void){
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)d[i]=-1;
    priority_queue<P>dik;
    for(int i=0;i<m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        g[--a].PB(P(--b,c));
        g[b].PB(P(a,c));
    }
    for(int i=0;i<k;i++){
        ll a,b;
        cin>>a>>b;
        d[--a]=b;
        dik.push(P(b,a));
    }
    while(!dik.empty()){
        ll v=dik.top().S,c=dik.top().F;
        dik.pop();
        if(d[v]>c)continue;
        for(int i=0;i<g[v].size();i++){
            ll u=g[v][i].F,l=g[v][i].S;
            if(d[u]<c-l){
                d[u]=c-l;
                dik.push(P(c-l,u));
            }
        }
    }
    int ans=0;
    for(int i=0;i<n;i++)if(d[i]>=0)ans++;
    cout<<ans<<endl;
}