Submission #1088373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088373		whtth	Valley (BOI19_valley)	C++14	36 / 100	70 ms	16488 KiB

valley

#include <bits/stdc++.h>
using namespace std;
long long n, q, d[1001][1001], inf=1e18+1, x[1001], y[1001], z[1001], f[1001], r, k, s, e;
vector <pair<long long, long long>>ke[1001];
void dij(int u, int f1, int f2){
    priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> qu;
    d[u][u]=0;
    qu.push({d[u][u], u});
    while(!qu.empty()){
        int t=qu.top().second, g=qu.top().first;
        qu.pop();
        if(g>d[u][t])continue;
        for(pair<long long, long long> v : ke[t]){
            if((t==f1 and v.first==f2)||(t==f2 and v.first==f1))continue;
            if(d[u][v.first]>d[u][t]+v.second){
                d[u][v.first]=d[u][t]+v.second;
                qu.push({d[u][v.first], v.first});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("valley.inp", "r", stdin);
    //freopen("valley.out", "w", stdout);
    cin>>n>>s>>q>>e;
     for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            d[i][j]=inf;
        }
    }
    for(int i=1;i<n;i++){
        cin>>x[i]>>y[i]>>z[i];
        ke[x[i]].push_back({y[i], z[i]});
        ke[y[i]].push_back({x[i], z[i]});
    }
    for(int i=1;i<=s;i++)cin>>f[i];
    for(int i=1;i<=q;i++){
        cin>>k>>r;
        dij(r, x[k], y[k]);
        if(d[r][e]!=inf)cout<<"escaped\n";
        else {
            long long ans=inf;
            for(int i=1;i<=s;i++){
                ans=min(ans, d[r][f[i]]);
            }
            if(ans!=inf)cout<<ans<<"\n";
            else cout<<"oo\n";
        }
        for(int i=1;i<=n;i++)d[r][i]=inf;
    }
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41