제출 #169473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169473		RafaelSus	Evacuation plan (IZhO18_plan)	C++14	100 / 100	896 ms	81984 KiB

plan

#include <bits/stdc++.h>
 
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);

int n,m,par[N],sz[N],k,up[20][N];
ll mn[20][N],tin[N],tout[N],timer;
ll dist[N];
vector<pair<int,ll>>g[N];
vector<pair<int,int>>road;

int find(int a){
  if(a==par[a])return a;
  return par[a]=find(par[a]);
}

void merge(int a,int b){
  a=find(a);b=find(b);
  if(sz[a]<sz[b])swap(a,b);
  sz[a]+=sz[b];
  par[b]=a;
}

void dfs(int v,int p,ll w){
  up[0][v]=p;
  mn[0][v]=w;
  tin[v]=++timer;
  for(int i=1;i<=19;i++){
    up[i][v]=up[i-1][up[i-1][v]];
    mn[i][v]=min(mn[i-1][v],mn[i-1][up[i-1][v]]);
  }
  for(auto to:g[v])
    if(to.first!=p)dfs(to.first,v,to.second);
  tout[v]=++timer;
}

bool upper(int a,int b){
  return tin[a]<=tin[b]&&tout[a]>=tout[b];
}

ll get(int a,int b){
  ll res=INF;
  if(upper(a,b)){
    for(int i=19;i>=0;--i){
      if(!upper(up[i][b],a)){
        res=min(res,mn[i][b]);
        b=up[i][b];
      }
    }
    res=min(res,mn[0][b]);
  }else if(upper(b,a)){
    for(int i=19;i>=0;--i){
      if(!upper(up[i][a],b)){
        res=min(res,mn[i][a]);
        a=up[i][a];
      }
    }
    res=min(res,mn[0][a]);
  }else{
    for(int i=19;i>=0;--i){
      if(!upper(up[i][b],a)){
        res=min(res,mn[i][b]);
        b=up[i][b];
      }
    }
    res=min(res,mn[0][b]);
    for(int i=19;i>=0;--i){
      if(!upper(up[i][a],b)){
        res=min(res,mn[i][a]);
        a=up[i][a];
      }
    }
    res=min(res,mn[0][a]);
  }
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  
  cin>>n>>m;
  for(int i=1;i<=n;i++){par[i]=i;sz[i]=1;}
  for(int i=0;i<m;i++){
    int a,b;ll c;
    cin>>a>>b>>c;
    g[a].pb({b,c});
    g[b].pb({a,c});
    road.pb({a,b});
  }  
  priority_queue<pair<ll,int>> q;
  cin>>k;
	memset(dist,0x3f3f3f3f,sizeof(dist));
  for(int i=0;i<k;i++){
    int v;cin>>v;
    dist[v]=0;q.push({0,v});
  }
  while(!q.empty()){
    int v=q.top().second;
    q.pop();
    for(auto x:g[v]){
      if(dist[x.first]>dist[v]+x.second){
        dist[x.first]=dist[v]+x.second;
        q.push({-dist[x.first],x.first});
      }
    }
  }
  for(int i=1;i<=n;i++)g[i].clear();
  vector<pair<ll,pair<int,int>>> vec;
  for(int i=0;i<m;i++)
    vec.pb({min(dist[road[i].first],dist[road[i].second]),{road[i].first,road[i].second}});
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  for(int i=0;i<m;i++){
    int a=vec[i].second.first,b=vec[i].second.second;
    ll w=min(dist[a],dist[b]);
    if(find(a)!=find(b)){
      g[a].pb({b,w});
      g[b].pb({a,w});
      merge(a,b);
    }
  }
  dfs(1,1,INF);
  int Q;
  cin>>Q;
  for(int i=0;i<Q;i++){
    int a,b;
    cin>>a>>b;
    cout<<get(a,b)<<'\n';
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46