이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
const int inf = 1e9;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
fast;
}
int RET = inf;
struct DSU
{
vi p,sz;
int n;
DSU(int _n)
{
n = _n;
p.assign(n + 1,-1);
sz.assign(n + 1,1);
for (int i = 0;i<=n;i++)p[i] = i;
}
int Find(int a)
{
if (p[a] == a)return a;
return p[a] = Find(p[a]);
}
void Unite(int a,int b)
{
a = Find(a),b = Find(b);
if (a == b)return;
if (sz[a] < sz[b])swap(a,b);
p[b] = a;
sz[b] += sz[a];
}
};
int n = 1e5 + 5,TIMER = 1;
vvvi adj(n),graph(n);
vi in(n),out(n),dist(n,inf);
vvi anc(n,vi(21)),dp(n,vi(21,inf)),edges,tree;
void dfs(int u,int p,ll w)
{
in[u] = TIMER++;
anc[u][0] = p;
dp[u][0] = w;
for (int i = 1;i<=20;i++){
anc[u][i] = anc[anc[u][i - 1]][i - 1];
dp[u][i] = min(dp[u][i - 1],dp[anc[u][i - 1]][i - 1]);
}
for (auto val:graph[u]){
int v = val[0],wt = val[1];
if (v == p)continue;
dfs(v,u,wt);
}
out[u] = TIMER++;
}
bool is_ancestor(int u,int v)
{
return in[u] <= in[v] && out[u] >= out[v];
}
int LCA(int u,int v)
{
if (is_ancestor(u,v))return u;
for (int i = 20;i>=0;i--)
if (!is_ancestor(anc[u][i],v)){
cout<<u<<" "<<i<<" "<<dp[u][i]<<endl;
RET = min(RET,dp[u][i]);
u = anc[u][i];
}
RET = min(RET,dp[u][0]);
return anc[u][0];
}
void query(int u,int v)
{
if (u == v)return;
for (int i = 20;i>=0;i--){
if (!is_ancestor(anc[u][i],v)){
RET = min(RET,dp[u][i]),u = anc[u][i];
}
}
RET = min(RET,dp[u][0]);
}
int main()
{
setIO();
int n,m,q,k;
cin>>n>>m;
priority_queue<pair<int,int>>qe;
while (m--){
int u,v,w;
cin>>u>>v>>w;
adj[u].pb({v,w}),adj[v].pb({u,w});
edges.pb({u,v});
}
cin>>k;
while (k--){
int u;
cin>>u;
dist[u] = 0;
qe.push({0,u});
}
while (!qe.empty()){
int u = qe.top().second;
int d = -qe.top().first;
qe.pop();
if (dist[u] != d)continue;
for (auto val:adj[u]){
int v = val[0];
int w = val[1];
if (dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
qe.push({-dist[v],v});
}
}
}
for (auto e:edges){
int u = e[0],v = e[1],w = min(dist[u],dist[v]);
tree.pb({w,u,v});
}
sort(tree.rbegin(),tree.rend());
DSU val(n);
for (auto it:tree){
int u = it[1],v = it[2],w = it[0];
if (val.Find(u) == val.Find(v))continue;
val.Unite(u,v);
graph[u].pb({v,w});
graph[v].pb({u,w});
}
dfs(1,1,inf);
cin>>q;
while (q--){
int u,v;
cin>>u>>v;
if (in[u] > in[v])swap(u,v);
RET = inf;
int l = LCA(u,v);
query(v,l);
cout<<RET<<endl;
}
return 0;
}
# | 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... |