#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const long long inf = (1LL << 61);
int n, m, k, q;
int startCities[maxn];
vector<pair<int, int>> g[maxn];
long long dist[maxn];
struct DSU
{
int par[maxn];
int dep[maxn];
void init()
{
for (int i = 1; i <= n; ++i)
{
par[i] = i;
dep[i] = 1;
}
}
int root(int node)
{
if (node == par[node])
{
return node;
}
return par[node] = root(par[node]);
}
void connect(int x, int y)
{
x = root(x);
y = root(y);
if (x == y)
{
return;
}
if (dep[x] >= dep[y])
{
par[y] = x;
if (dep[x] == dep[y])
{
++dep[x];
}
}
else
{
par[x] = y;
}
}
bool areConnected(int x, int y)
{
return root(x) == root(y);
}
};
DSU dsu;
vector<long long> toTry;
struct Edge
{
int from;
int to;
long long w;
Edge()
{
}
Edge(int _from, int _to, long long _w)
{
from = _from;
to = _to;
w = _w;
}
bool operator < (const Edge& other) const
{
return w < other.w;
}
};
vector<Edge> edges;
bool check(int from, int to, long long minW)
{
//cout << "checking for " << minW << endl;
dsu.init();
int l = 0;
int r = m - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (edges[mid].w >= minW)
{
r = mid - 1;
}
else
{
l = mid + 1;
}
}
for (int i = l; i < m; ++i)
{
//cout << "add edge " << edges[i].from << ' ' << edges[i].to << ' ' << edges[i].w << endl;
dsu.connect(edges[i].from, edges[i].to);
}
return dsu.areConnected(from, to);
}
long long solve(int from, int to)
{
//cout << "query " << from << " " << to << endl;
int l = 0;
int r = toTry.size() - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(from, to, toTry[mid]) == true)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return toTry[r];
}
vector<long long> uniqueDistances()
{
set<long long> s;
vector<long long> res;
for (int i = 1; i <= n; ++i)
{
if (s.find(dist[i]) == s.end())
{
s.insert(dist[i]);
}
}
for (auto element : s)
{
res.push_back(element);
}
return res;
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int x, y, w;
cin >> x >> y >> w;
g[x].push_back(make_pair(y, w));
g[y].push_back(make_pair(x, w));
}
cin >> k;
for (int i = 1; i <= k; ++i)
{
cin >> startCities[i];
}
for (int i = 1; i <= n; ++i)
{
dist[i] = inf;
}
priority_queue<pair<long long, int>> pq;
for (int i = 1; i <= k; ++i)
{
pq.push(make_pair(0, startCities[i]));
dist[startCities[i]] = 0;
}
while (!pq.empty())
{
int node = pq.top().second;
long long curr = -pq.top().first;
pq.pop();
for (int i = 0; i < g[node].size(); ++i)
{
long long path = g[node][i].second + curr;
int to = g[node][i].first;
if (dist[to] > path)
{
dist[to] = path;
pq.push(make_pair(-path, to));
}
}
}
/*cout << "check " << endl;
for (int i = 1; i <= n; ++i)
{
cout << dist[i] << ' ';
}
cout << endl;*/
toTry = uniqueDistances();
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j < g[i].size(); ++j)
{
if (i < g[i][j].first)
{
edges.push_back(Edge(i, g[i][j].first, min(dist[i], dist[g[i][j].first])));
}
}
}
sort(edges.begin(), edges.end());
cin >> q;
for (int i = 1; i <= q; ++i)
{
int from, to;
cin >> from >> to;
cout << solve(from, to) << "\n";
}
return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:225:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
225 | for (int i = 0; i < g[node].size(); ++i)
| ~~^~~~~~~~~~~~~~~~
plan.cpp:251:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
251 | for (int j = 0; j < g[i].size(); ++j)
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
10 ms |
4696 KB |
Output is correct |
3 |
Correct |
10 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
10 ms |
4684 KB |
Output is correct |
6 |
Correct |
9 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
23 ms |
4696 KB |
Output is correct |
10 |
Correct |
11 ms |
4664 KB |
Output is correct |
11 |
Correct |
22 ms |
4444 KB |
Output is correct |
12 |
Correct |
10 ms |
4696 KB |
Output is correct |
13 |
Correct |
23 ms |
4444 KB |
Output is correct |
14 |
Correct |
22 ms |
4444 KB |
Output is correct |
15 |
Correct |
23 ms |
4692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
10 ms |
4696 KB |
Output is correct |
3 |
Correct |
10 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
10 ms |
4684 KB |
Output is correct |
6 |
Correct |
9 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
23 ms |
4696 KB |
Output is correct |
10 |
Correct |
11 ms |
4664 KB |
Output is correct |
11 |
Correct |
22 ms |
4444 KB |
Output is correct |
12 |
Correct |
10 ms |
4696 KB |
Output is correct |
13 |
Correct |
23 ms |
4444 KB |
Output is correct |
14 |
Correct |
22 ms |
4444 KB |
Output is correct |
15 |
Correct |
23 ms |
4692 KB |
Output is correct |
16 |
Execution timed out |
4064 ms |
11108 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4440 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
17572 KB |
Output is correct |
2 |
Correct |
295 ms |
29348 KB |
Output is correct |
3 |
Correct |
253 ms |
29548 KB |
Output is correct |
4 |
Correct |
79 ms |
14796 KB |
Output is correct |
5 |
Correct |
277 ms |
29556 KB |
Output is correct |
6 |
Correct |
246 ms |
29308 KB |
Output is correct |
7 |
Correct |
274 ms |
30760 KB |
Output is correct |
8 |
Correct |
234 ms |
29736 KB |
Output is correct |
9 |
Correct |
261 ms |
28996 KB |
Output is correct |
10 |
Correct |
258 ms |
28948 KB |
Output is correct |
11 |
Correct |
265 ms |
30032 KB |
Output is correct |
12 |
Correct |
260 ms |
28856 KB |
Output is correct |
13 |
Correct |
264 ms |
29260 KB |
Output is correct |
14 |
Correct |
248 ms |
29516 KB |
Output is correct |
15 |
Correct |
329 ms |
30020 KB |
Output is correct |
16 |
Correct |
254 ms |
30724 KB |
Output is correct |
17 |
Correct |
262 ms |
30484 KB |
Output is correct |
18 |
Correct |
262 ms |
30536 KB |
Output is correct |
19 |
Correct |
68 ms |
14980 KB |
Output is correct |
20 |
Correct |
256 ms |
29292 KB |
Output is correct |
21 |
Correct |
225 ms |
29676 KB |
Output is correct |
22 |
Correct |
49 ms |
13124 KB |
Output is correct |
23 |
Correct |
80 ms |
13772 KB |
Output is correct |
24 |
Correct |
53 ms |
12984 KB |
Output is correct |
25 |
Correct |
54 ms |
13116 KB |
Output is correct |
26 |
Correct |
72 ms |
11968 KB |
Output is correct |
27 |
Correct |
80 ms |
14900 KB |
Output is correct |
28 |
Correct |
49 ms |
13124 KB |
Output is correct |
29 |
Correct |
80 ms |
14988 KB |
Output is correct |
30 |
Correct |
52 ms |
13124 KB |
Output is correct |
31 |
Correct |
85 ms |
14968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
10 ms |
4696 KB |
Output is correct |
3 |
Correct |
10 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
10 ms |
4684 KB |
Output is correct |
6 |
Correct |
9 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
23 ms |
4696 KB |
Output is correct |
10 |
Correct |
11 ms |
4664 KB |
Output is correct |
11 |
Correct |
22 ms |
4444 KB |
Output is correct |
12 |
Correct |
10 ms |
4696 KB |
Output is correct |
13 |
Correct |
23 ms |
4444 KB |
Output is correct |
14 |
Correct |
22 ms |
4444 KB |
Output is correct |
15 |
Correct |
23 ms |
4692 KB |
Output is correct |
16 |
Execution timed out |
4064 ms |
11108 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |