Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAXN 100005
- #define INF 0x3f3f3f3f
- using namespace std;
- long long n, m, k, d[MAXN], viz[MAXN], s;
- struct edge
- {
- char special; // 0 - normal, 1 - special
- long long nod,c;
- edge(long long nod, long long c, char special):nod(nod),c(c),
- special(special) {}
- bool operator<(const edge &oth) const
- {
- if(c == oth.c) {
- if(special == 1)
- return -1;
- }
- return c>oth.c;
- }
- };
- vector<edge> v[MAXN];
- priority_queue<edge> pq;
- void djikstra(long long start)
- {
- for(long long i=1; i<=n; ++i) {
- d[i]=INF;
- viz[i] = 0;
- }
- d[start]=0;
- pq.push(edge(start,0,0));
- while(!pq.empty())
- {
- long long nod = pq.top().nod;
- long long cost = pq.top().c;
- long long special = pq.top().special;
- //cout << "nod : " << nod << " special " << special << endl;
- pq.pop();
- if(viz[nod] == 0) {
- viz[nod] = 1;
- for(edge i : v[nod]) {
- if(d[nod] + i.c < d[i.nod]) {
- d[i.nod] = d[nod] + i.c;
- if(i.special) {
- ++s;
- }
- pq.push(edge(i.nod, d[i.nod], 0));
- }
- }
- }
- }
- }
- int main()
- {
- cin>>n>>m>>k;
- s = 0;
- for(long long i=1; i<=m; ++i)
- {
- long long a,b,c;
- cin>>a>>b>>c;
- v[a].push_back(edge(b, c, 0));
- }
- for(long long i = 1; i <= k; ++i)
- {
- long long a, b;
- cin >> a >> b;
- d[a] = b;
- v[1].push_back(edge(a, b, 1));
- // pq.push(edge(a,b,1));
- }
- djikstra(1);
- cout << k - s << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement