#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1001000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define all(s) s.begin(), s.end()
using namespace std;
int n, m;
vector<pp> e[N];
priority_queue<pp> heap;
long long d[N];
int fUnion[N], p[N];
vector<int> Query[N];
int l[N], r[N], s[N], t[N], cur[N];
bool mark[N];
void Union(int a, int b) {
int t = fUnion[a] + fUnion[b];
if (fUnion[a] > fUnion[b]) swap(a, b);
fUnion[a] = t;
fUnion[b] = a;
}
int root(int u) { return fUnion[u] < 0 ? u : (fUnion[u] = root(fUnion[u])); }
int main() {
scanf("%d %d", &n, &m);
REP(i, m) {
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
e[u].push_back(pp(v, c));
e[v].push_back(pp(u, c));
}
int k;
scanf("%d", &k);
FOR(i, 1, n) d[i] = 1e18;
REP(i, k) {
int x;
cin >> x;
heap.push(pp(d[x] = 0, x));
}
while (!heap.empty()) {
int u = heap.top().second;
long long dis = -heap.top().first;
heap.pop();
if (dis != d[u]) continue;
for (pp t : e[u]) {
long long newD = d[u] + t.second;
int v = t.first;
if (d[v] > newD) heap.push(pp(-(d[v] = newD), v));
}
}
FOR(i, 1, n) p[i] = i;
Arr(p, 1, n);
Arr(d, 1, n);
sort(p + 1, p + n + 1, [] (const int &a, const int &b) {
return d[a] > d[b];
});
Arr(p, 1, n);
//Read query
int q;
scanf("%d", &q);
FOR(i, 1, q) scanf("%d %d", &s[i], &t[i]);
//Parallel Binary Search
FOR(i, 1, q) l[i] = 1, r[i] = n;
bool changed = true;
while (changed) {
changed = false;
FOR(i, 1, n) {
Query[i].clear();
fUnion[i] = -1;
mark[i] = false;
}
FOR(i, 1, q) if (l[i] <= r[i]) {
Query[(l[i] + r[i]) >> 1].push_back(i);
changed = true;
}
FOR(i, 1, n) {
int u = p[i];
mark[u] = true;
for (pp t : e[u]) {
int v = t.first;
if (mark[v]) {
int a = root(u);
int b = root(v);
if (a != b) Union(a, b);
}
}
for (int x : Query[i]) {
if (root(s[x]) == root(t[x])) cur[x] = i, r[x] = i - 1;
else l[x] = i + 1;
}
}
}
FOR(i, 1, q) printf("%lld\n", d[p[cur[i]]]);
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
plan.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
plan.cpp:72:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
FOR(i, 1, q) scanf("%d %d", &s[i], &t[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
47352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
47352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
47452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2052 ms |
58080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
47352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
