Submission #1130385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130385		harut_13	Evacuation plan (IZhO18_plan)	C++20	10 / 100	515 ms	589824 KiB

plan

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <string>
#include <ios>
#include <iomanip>
#include <deque>
#include <queue>
#include <list> 
#include <stack>

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(NULL);
#define CY   cout<<"YES"<<endl
#define CN   cout<<"NO"<<endl
#define ll   long long
#define ciN  cin
#define itn  int
#define pshb  push_back
#define sz  size()
#define vec vector<int>
#define vecl vector<long long>
#define fro for
#define Int int
#define stirng string
#define nedl   endl 
#define pi 3.141592653589793238463
#define endl '\n'
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MOD 1000000007


using namespace std;

ll gcd(ll n1, ll n2)
{
    if (n2 != 0)
        return gcd(n2, n1 % n2);
    else
        return n1;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}

ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = (pv(a, b / 2));
    if (b % 2) {
        return ((res) * (res) * (a));
    }
    else {
        return (res) * (res);
    }
}
void solve() {
    int n, m; cin >> n >> m;
    vector<vector<pll>> gp(n);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        gp[--u].pshb({ --v,w });
        gp[v].pshb({ u,w });
    }
    int k; cin >> k;
    vec v(k);
    for (int i = 0; i < k; i++) {
        cin >> v[i];
        v[i]--;
    }
    int q; cin >> q;
    vector<pii> harc(q);
    for (int i = 0; i < q; i++) {
        cin >> harc[i].first;
        cin >> harc[i].second;
        harc[i].first--;
        harc[i].second--;
    }
    vector<vecl> d(k, vecl(n,1e18));
    for (int i = 0; i < k; i++) {
        int gag = v[i];
        priority_queue<pll> pq;
        d[i][gag] = 0;
        pq.push({ 0,gag });
        while (pq.sz) {
            ll dist =-1*pq.top().first;
            ll u = pq.top().second;
            //cout << "??" << u << " " << dist << endl;
            pq.pop();
            if (dist != d[i][u])continue;
            for (int j = 0; j < gp[u].sz; j++) {
                int to = gp[u][j].first;
                ll w = gp[u][j].second;
                if (dist + w < d[i][to]) {
                    d[i][to] = dist + w;
                    pq.push({ -1 * d[i][to],to });
                }
            }
        }
        cout << endl;
    }
    vecl mn(n,1e18);
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n; j++) {
            mn[j] = min(mn[j], d[i][j]);
        }
        cout << endl;
    }
    for (int i = 0; i < q; i++) {
        cout << min(mn[harc[i].first], mn[harc[i].second]) << endl;
    }
}



signed main() { 
    FASTIO
        //int t; cin >> t;
    //while (t--)
        solve();


}

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