제출 #1350687

#제출 시각아이디문제언어결과실행 시간메모리
1350687mikasaValley (BOI19_valley)C++20
36 / 100
3094 ms12976 KiB
#include<bits/stdc++.h>
using namespace std;
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define int long long
#define all(x,off) x.begin()+off,x.end()
#define pb push_back 

const int N=1e6+10;
const int inf=9e17;
const int mod=1e9+7;
int n,m,q,k;

int sh[N];
int x[N],y[N],z[N];
vector<array<int,2>> g[N];

int dij(int s,int idx) {
  vector<int> d(n+1,inf);
  d[s]=0;
  priority_queue<array<int,2>> q;
  q.push({0,s});
  while(!q.empty()) {
    auto [dis,u]=q.top();
    q.pop();
    if (-dis>d[u]) continue;
    for (auto [v,w]:g[u]) {
      if (min(u,v)==x[idx]&&max(u,v)==y[idx]) continue;
      if (d[v]>d[u]+w) {
        d[v]=d[u]+w;
        q.push({-d[v],v});
      }
    }
  }
  if (d[k]!=inf) return -1;
  int dis=inf;
  for (int i=1;i<=n;++i) {
    if (sh[i]) dis=min(dis,d[i]);
  }
  return dis;
}

void levi() {
  cin>>n>>m>>q>>k;
  for (int i=1;i<=n-1;++i) {
    int u,v,w;
    cin>>u>>v>>w;
    if (u>v) swap(u,v);
x[i]=u;
y[i]=v;;z[i]=w;
    g[u].pb({v,w});
    g[v].pb({u,w});
  }
  for (int i=1,x;i<=m;++i) {
    cin>>x;
    sh[x]=1;
  }
  for (int j=1;j<=q;++j) {
    int i,s;
    cin>>i>>s;
    int res=dij(s,i);
    if (res==-1) {
      cout<<"escaped\n";
      continue;
    }
    if (res==inf) {
      cout<<"oo\n";
      continue;
    }
    cout<<res<<'\n';
  }
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);int tt=1;//cin>>tt;
  while (tt--) levi();
}

/*


*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...