Submission #338450

#TimeUsernameProblemLanguageResultExecution timeMemory
338450BY_KUTBILIMEvacuation plan (IZhO18_plan)C++14
23 / 100
637 ms19428 KiB
/** @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);
    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});
    }
    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--;
        cout << min(d[t], d[s]) << endl;
    }
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...