Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <stdio.h>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <set>
- #include <map>
- #include <string>
- #include <math.h>
- #include <cassert>
- #define pb push_back
- #define mp make_pair
- #define forn(i, n) for(int i = 0; i < (int)(n); i++)
- #define X first
- #define Y second
- #define sz(a) (int)((a).size())
- #define all(a) (a).begin(), (a).end()
- using namespace std;
- typedef long long li;
- typedef long double ld;
- typedef pair<int, int> pt;
- const int INF = (int)(1e9);
- const li INF64 = (li)(INF) * (li)(INF);
- const ld eps = 1e-9;
- const ld pi = (ld)(3.1415926535897932384626433832795);
- const int dx4[] = {-1, 0, 1, 0};
- const int dy4[] = {0, 1, 0, -1};
- const int ddx[] = {-1, 1, 1, -1};
- const int ddy[] = {1, 1, -1, -1};
- const int N = 1e5;
- vector<pair<int, int> > g[N];
- int n, m, A, k;
- bool used[N];
- int dist[N];
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- while(cin >> n >> m >> A >> k)
- {
- if(n + m + A + k == 0)
- break;
- for(int i = 0; i < N; i++)
- g[i].clear();
- memset(used, false, sizeof used);
- memset(dist, -1, sizeof dist);
- forn(i, m)
- {
- int a, b, w;
- scanf("%d %d %d", &a, &b, &w);
- g[a].pb(mp(b, w));
- g[b].pb(mp(a, w));
- }
- int sz = n;
- forn(kk, A)
- {
- int v;
- scanf("%d", &v);
- queue<int> q;
- q.push(v);
- if(!used[v])
- {
- used[v] = true;
- sz--;
- }
- dist[v] = 0;
- while(!q.empty())
- {
- int v = q.front();
- q.pop();
- forn(i, g[v].size())
- {
- int to = g[v][i].X;
- int cost = g[v][i].Y;
- if(dist[v] + cost < k && (dist[v] + cost < dist[to] || dist[to] == -1))
- {
- dist[to] = dist[v] + cost;
- q.push(to);
- if(!used[to])
- {
- used[to] = true;
- sz--;
- }
- }
- }
- }
- printf("%d ", sz);
- }
- printf("\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement