이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//####################
//IZHO_2018_Plan
//####################
#include<bits/stdc++.h>
/*
Plan
Djikstra OK
KRUSKAL
LCA
SPARSE-TABLE
*/
#define int long long
using namespace std;
const int INF=1e18;
const int maxiNode = 2*100*1000;
vector<pair<int,int>> links[maxiNode];
struct UnionFind{
vector<int> chef;
UnionFind(int _size){
chef.resize(_size);
for(int i=0;i<_size;i++){
chef[i]=i;
}
}
int find(int a){
if(chef[a]==a)return a;
else return chef[a]=find(chef[a]);
}
bool fusion(int a,int b){
int ra = find(a);
int rb = find(b);
if(ra!=rb){
chef[ra]=rb;
return true;
}else{
return false;
}
}
};
int minimal_distance[maxiNode];
bool comp(pair<int,int> &a,pair<int,int> &b){
int ra = min(minimal_distance[a.first],minimal_distance[a.second]);
int rb = min(minimal_distance[b.first],minimal_distance[b.second]);
return ra>rb;
}
vector<int> linksTree[maxiNode];
const int LOG = 20;
int up[LOG][maxiNode];
int depth[maxiNode];
void root_the_tree(int node,int dad=-1,int deep=0){
up[0][node]=dad;
depth[node]=deep;
for(int v:linksTree[node])if(dad!=v){
root_the_tree(v,node,deep+1);
}
}
int getKancestor(int node,int k){
for(int b=LOG-1;b>=0;b--){
if((k>>b)&1){
node = up[b][node];
if(node==-1)return -1;
}
}
return node;
}
int lca(int a,int b){
if(depth[a]<depth[b])swap(a,b);
a=getKancestor(a,depth[a]-depth[b]);
if(a==b){
return a;
}else{
for(int l = LOG-1 ; l>=0 ; l--){
if(up[l][a] != up[l][b]){
a = up[l][a];
b = up[l][b];
}
}
return up[0][a];
}
}
int mini[LOG][maxiNode];
int getMini(int node,int k){
int re = mini[0][node];
for(int b=LOG-1;b>=0;b--){
if((k>>b)&1){
re = min(re,mini[b][node]);
node = up[b][node];
if(node==-1)break;;
}
}
return re;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;cin>>n>>m;
vector<pair<int,int>> edges;
for(int i = 0;i<m;i++){
int a,b,w;
cin>>a>>b>>w;
a--;b--;
links[a].push_back({b,w});
links[b].push_back({a,w});
edges.push_back({a,b});
}
int k;cin>>k;
vector<int> infected(k);
for(int i=0;i<k;i++){
cin>>infected[i];
infected[i]--;
}
//Djikstra multi-source
priority_queue<pair<int,int>> PQ;
for(int i=0;i<k;i++){
PQ.push({-0,infected[i]});
}
fill(minimal_distance,minimal_distance+n,-1);
while(!PQ.empty()){
pair<int,int> act = PQ.top();
PQ.pop();
if(minimal_distance[act.second]!=-1){
continue;
}else{
minimal_distance[act.second] = act.first * -1;
for(auto p:links[act.second]){
PQ.push({(minimal_distance[act.second]+p.second)*-1,p.first});
}
}
}
UnionFind UF(n);
sort(edges.begin(),edges.end(),comp);
for(int i=0;i<m;i++){
pair<int,int> &act = edges[i];
if(UF.fusion(act.first,act.second)){
// cout<<act.first<<' '<<act.second<<endl;
linksTree[act.first].push_back(act.second);
linksTree[act.second].push_back(act.first);
}
}
root_the_tree(0);
for(int l=1;l<LOG;l++){
for(int i=0;i<n;i++){
if(up[l-1][i]==-1){
up[l][i]=-1;
continue;
}
up[l][i] = up[l-1][up[l-1][i]];
}
}
for(int i=0;i<n;i++){
mini[0][i] = minimal_distance[i];
}
for(int l=1;l<LOG;l++){
for(int i=0;i<n;i++){
if(up[l-1][i]==-1){
mini[l][i]=mini[l-1][i];
continue;
}
mini[l][i] = min(mini[l-1][i],mini[l-1][up[l-1][i]]);
}
}
int q;cin>>q;
for(int i=0;i<q;i++){
int a,b;cin>>a>>b;
a--;
b--;
int LCA = lca(a,b);
int ans = INF;
ans = min(ans, getMini(a,depth[a]-depth[LCA]));
ans = min(ans, getMini(b,depth[b]-depth[LCA]));
cout<<ans<<'\n';;
}
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... |