Submission #679432

#	Time	Username	Problem	Language	Result	Execution time	Memory
679432		Chal1shkan	Evacuation plan (IZhO18_plan)	C++14	23 / 100	866 ms	41164 KiB

plan

#include <bits/stdc++.h>

# define pb push_back
# define ff first
# define ss second
# define nl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll maxn = 1e5 + 25;
const ll maxl = 22 + 0;
const ll inf = 1e18 + 0;
const ll mod = 998244353;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;

ll n, m, k, q, d[maxn];
vector <pair <ll, ll> > g[maxn];

void dijkstra (ll s)
{
    d[s] = 0;
    set <pair <ll, ll> > q;
    q.insert({0, s});
    while (!q.empty())
    {
        ll v = q.begin() -> ss;
        q.erase(q.begin());
        for (auto i : g[v])
        {
            ll to = i.ff, w = i.ss;
            if (d[v] + w < d[to])
            {
                q.erase({d[to], to});
                d[to] = d[v] + w;
                q.insert({d[to], to});
            }
        }
    }
}

void ma1n ()
{
    cin >> n >> m;
    for (ll i = 1; i <= n; ++i) d[i] = inf;
    for (ll i = 1; i <= m; ++i)
    {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    cin >> k;
    for (ll i = 1; i <= k; ++i)
    {
        ll v;
        cin >> v;
        dijkstra(v);
    }
    cin >> q;
    for (ll i = 1; i <= q; ++i)
    {
        ll u, v;
        cin >> u >> v;
        cout << min(d[u], d[v]) << nl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    // freopen("mooyomooyo.in", "r", stdin);
    // freopen("mooyomooyo.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << nl;
        ma1n();
    }
    return 0;
}

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