Submission #338449

#	Time	Username	Problem	Language	Result	Execution time	Memory
338449		BY_KUTBILIM	Evacuation plan (IZhO18_plan)	C++14	10 / 100	238 ms	524292 KiB

plan

/** @BY_KUTBILIM **/
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).end()

const int inf = (int)1e9+7;

vector<vector<pair<int,int>>> g;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie();

    int n, m;
    cin >> n >> m;
    g.resize(n);
    vector<vector<int>> road(n, vector<int> (n, 0));
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> v >> u >> w;
        v--;
        u--;
        g[v].pb({u, w});
        g[u].pb({v, w});
        road[v][u] = road[u][v] = 1;
    }
    int k;
    cin >> k;
    int r[k];
    priority_queue<pair<int,int>> q;
    vector<int> d(n, inf), used(n, 0);
    for(int i = 0; i < k; i++){
        cin >> r[i];
        r[i]--;
        q.push({0, r[i]});
        d[r[i]] = 0;
    }
    while(!q.empty()){
        int a = q.top().second; q.pop();
        if(used[a]) continue;
        for(auto u : g[a]){
            int b = u.first, w = u.second;
            if(d[a] + w < d[b]){
                d[b] = d[a] + w;
                q.push({-d[b], b});
            }
        }
    }
    int Q;
    cin >> Q;
    while(Q--){
        int s, t;
        cin >> s >> t;
        s--;
        t--;
        if(road[s][t]){
            cout << min(d[s], d[t]) << endl;
        } else{
            
        }
    }
    
    return 0;
}

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