Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <unordered_set>
- using namespace std;
- #define int long long
- #define vi vector <int>
- #define pb(a) push_back(a)
- #define all(v) v.begin(), v.end()
- #define pii pair <int, int>
- #define mp(a, b) make_pair(a, b)
- const int INF = 1e9 + 9;
- const int MAXN = 1e6 + 2;
- int n, m, k, q;
- vector <vector <pii> > g, gt;
- vector <vi> d;
- vi used, hubs;
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cin >> n >> m >> k >> q;
- g.resize(n);
- gt.resize(n);
- used.resize(n, 0);
- hubs.resize(k, 0);
- d.resize(k, vi(k, INF));
- for (int i = 0; i < m; ++i) {
- int u, v, cost;
- cin >> u >> v >> cost;
- g[u - 1].pb(mp(v - 1, cost));
- gt[v - 1].pb(mp(u - 1, cost));
- }
- for (int i = 0; i < k; ++i) {
- cin >> hubs[i];
- hubs[i]--;
- }
- vi ishub(n);
- for (int i = 0; i < k; ++i)
- ishub[hubs[i]] = 1;
- vector <vi> d(k, vi(n, INF)), dt(k, vi(n, INF));
- for (int i = 0; i < k; ++i){
- d[i][hubs[i]] = 0;
- set <pii> s;
- s.insert({0, hubs[i]});
- while (!s.empty()){
- auto v = *s.begin();
- s.erase(s.begin());
- for (auto to : g[v.second]){
- if (d[i][v.second] + to.second < d[i][to.first]){
- s.erase({ d[i][to.first], to.first });
- d[i][to.first] = d[i][v.second] + to.second;
- s.insert({ d[i][to.first], to.first });
- }
- }
- }
- }
- for (int i = 0; i < k; ++i){
- dt[i][hubs[i]] = 0;
- set <pii> s;
- s.insert({ 0, hubs[i] });
- while (!s.empty()){
- auto v = *s.begin();
- s.erase(s.begin());
- for (auto to : gt[v.second]){
- if (dt[i][v.second] + to.second < dt[i][to.first]){
- s.erase({ dt[i][to.first], to.first });
- dt[i][to.first] = dt[i][v.second] + to.second;
- s.insert({ dt[i][to.first], to.first });
- }
- }
- }
- }
- int cnt = 0, ans = 0;
- for (int j = 0; j < q; ++j){
- int u, v;
- cin >> u >> v;
- --u, --v;
- if (u == v){
- ++cnt;
- }
- else{
- int uis = -1, vis = -1;
- for (int i = 0; i < k; ++i){
- if (hubs[i] == u)
- uis = i;
- if (hubs[i] == v)
- vis = i;
- }
- if (uis != -1 && vis != -1){
- if (d[uis][v] < INF){
- ++cnt;
- ans += d[uis][v];
- }
- }
- else if (uis != -1){
- if (d[uis][v] < INF){
- ++cnt;
- ans += d[uis][v];
- }
- }
- else if (vis != -1){
- int mini = INF;
- for (int cur = 0; cur < k; ++cur){
- if (d[cur][v] < INF)
- mini = min(mini, d[cur][v]);
- }
- if (mini < INF){
- ++cnt;
- ans += mini;
- }
- }
- else{
- int mini = INF;
- for (int cur = 0; cur < k; ++cur){
- if (dt[cur][u] < INF && d[cur][v] < INF)
- mini = min(mini, dt[cur][u] + d[cur][v]);
- }
- if (mini < INF){
- ++cnt;
- ans += mini;
- }
- }
- }
- }
- cout << cnt << '\n' << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement