This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int INF = 1e9;
int n, m, k, q;
int d[MAXN];
int l[MAXN], r[MAXN];
int uu[MAXN], vv[MAXN], dsu[MAXN];
vector <pair <int, int> > Adj[MAXN];
int Root(int node)
{
return dsu[node] == node ? node : dsu[node] = Root(dsu[node]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int u, v, c;
cin >> u >> v >> c;
Adj[u].emplace_back(v, c);
Adj[v].emplace_back(u, c);
}
for(int i = 1; i <= n; i++)
{
d[i] = INF;
}
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
cin >> k;
for(int i = 1; i <= k; i++)
{
int a;
cin >> a;
d[a] = 0;
pq.emplace(0, a);
}
while(pq.empty() == false)
{
int dd = pq.top().first, node = pq.top().second;
pq.pop();
if(dd == d[node])
{
for(auto x : Adj[node])
{
if(d[x.first] > d[node] + x.second)
{
d[x.first] = d[node] + x.second;
pq.emplace(d[x.first], x.first);
}
}
}
}
vector <pair <int, int> > V;
for(int i = 1; i <= n; i++)
{
V.emplace_back(d[i], i);
}
sort(V.rbegin(), V.rend());
cin >> q;
for(int i = 1; i <= q; i++)
{
cin >> uu[i] >> vv[i];
l[i] = 0, r[i] = 1e9;
}
for(int times = 1; times <= 30; times++)
{
vector <pair <int, int> > Queries;
for(int i = 1; i <= n; i++)
{
dsu[i] = i;
}
for(int i = 1; i <= q; i++)
{
int mid = (l[i] + r[i] + 1) >> 1;
Queries.emplace_back(mid, i);
}
sort(Queries.rbegin(), Queries.rend());
int pt = 0;
for(auto x : Queries)
{
while(pt < n and V[pt].first >= x.first)
{
for(auto x : Adj[V[pt].second])
{
int u = x.first, v = V[pt].second;
if(d[u] > d[v])
{
u = Root(u), v = Root(v);
if(u != v)
{
dsu[u] = v;
}
}
}
pt++;
}
if(Root(uu[x.second]) == Root(vv[x.second]))
{
l[x.second] = x.first;
}
else
{
r[x.second] = x.first - 1;
}
}
}
for(int i = 1; i <= q; i++)
{
cout << l[i] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |