Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- typedef pair<int,int> ii;
- typedef pair<int,ii> data;
- #define fi first
- #define se second
- const int N = 25e4 + 5;
- int n, m, k;
- vector<ii> adj[N];
- int a[N];
- int f[N], root[N];
- bool visit[N];
- int res[N];
- priority_queue<data, vector<data>, greater<data> > pq;
- void solve(int u) {
- if (visit[u]) return;
- visit[u] = true;
- long long val = 0;
- for (auto v : adj[u]) {
- if (root[v.fi] == root[u]) {
- if (f[v.fi] + v.se == f[u]) continue;
- val += 2LL * v.se;
- solve(v.fi);
- }
- else {
- int tmp = f[u] + f[v.fi] + v.se;
- val += tmp - 2LL * f[u];
- }
- }
- res[root[u]] += val;
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin >> n >> m;
- for (int i = 1;i <= m;++i) {
- int u, v, w; cin >> u >> v >> w;
- adj[u].push_back({v, w}), adj[v].push_back({u, w});
- }
- for (int i = 1;i <= n;++i) f[i] = 1e18, root[i] = n + 1;
- cin >> k;
- for (int i = 1;i <= k;++i) {
- cin >> a[i];
- f[a[i]] = 0, root[a[i]] = a[i];
- pq.push({0, {a[i], a[i]}});
- }
- while (!pq.empty()) {
- data cur = pq.top(); pq.pop();
- if (root[cur.se.se] != cur.se.fi || f[cur.se.se] != cur.fi) continue;
- int u = cur.se.se;
- for (auto v : adj[u]) {
- if (f[v.fi] > f[u] + v.se || (f[v.fi] == f[u] + v.se && root[u] < root[v.fi])) {
- f[v.fi] = f[u] + v.se, root[v.fi] = root[u];
- pq.push({f[v.fi], {root[v.fi], v.fi}});
- }
- }
- }
- // for (int i = 1;i <= n;++i) cout << root[i] << '\n';
- for (int i = 1;i <= k;++i) {
- solve(a[i]); cout << res[a[i]] / 2LL;
- if (res[a[i]] & 1LL) cout << ".5" << '\n';
- else cout << ".0" << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement