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>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
int n, m, k, q;
const int INF = 1e9;
vector<pair<int, int>> adj[100005];
int dist[100005];
priority_queue<pair<int, int>> pq;
vector<int> qry[100005], parent;
vector<int> moment[100005], minm[100005];
int siz[100005], minn[100005], tin[100005];
void init()
{
parent.resize(n + 1);
for(int i = 1; i <= n; i++)
parent[i] = i, siz[i] = 1, tin[i] = 0, minn[i] = dist[i];
}
int cauta(int u, int timer)
{
if(parent[u] == u || tin[u] > timer)
return u;
return cauta(parent[u], timer);
}
bool cmp(int a, int b)
{
return dist[a] > dist[b];
}
void unite(int u, int v, int t)
{
u = cauta(u, t);
v = cauta(v, t);
if(u == v)
return;
if(siz[u] > siz[v])
swap(u, v);
moment[v].push_back(t);
minn[v] = min(minn[v], minn[u]);
minm[v].push_back(minn[v]);
tin[u] = t;
parent[u] = v;
siz[v] += siz[u];
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int a, b, c;
cin>>a>>b>>c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
cin>>k;
vector<int> aux;
for(int i = 1; i <= n; i++)
dist[i] = INF, aux.push_back(i);
for(int i = 1; i <= k; i++)
{
int a;
cin>>a;
pq.push({0, a});
dist[a] = 0;
}
while(!pq.empty())
{
int nod = pq.top().second;
int d = pq.top().first;
pq.pop();
if(dist[nod] != d)
continue;
for(auto it : adj[nod])
if(dist[nod] + it.second < dist[it.first])
dist[it.first] = dist[nod] + it.second, pq.push({dist[it.first], it.first});
}
init();
sort(aux.begin(), aux.end(), cmp);
int cnt = 0;
for(int i = 0; i < n; i++)
{
for(auto it : adj[aux[i]])
if(dist[it.first] >= dist[aux[i]])
unite(it.first, aux[i], ++cnt);
}
cin>>q;
for(int i = 1; i <= q; i++)
{
int a, b;
cin>>a>>b;
int st = 1, dr = cnt, rez, nod;
while(st <= dr)
{
int mij = (st + dr) / 2;
int u = cauta(a, mij), v = cauta(b, mij);
if(u != v) st = mij + 1;
else dr = mij - 1, rez = mij, nod = u;
}
int poz = upper_bound(moment[nod].begin(), moment[nod].end(), rez) - moment[nod].begin();
cout<<min(min(dist[a], dist[b]), minm[nod][poz - 1])<<'\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
*/
# | 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... |