Submission #893882

#	Time	Username	Problem	Language	Result	Execution time	Memory
893882		borisAngelov	Evacuation plan (IZhO18_plan)	C++17	41 / 100	4034 ms	27876 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const long long inf = (1LL << 61);

int n, m, k, q;

int startCities[maxn];

vector<pair<int, int>> g[maxn];

long long dist[maxn];

long long ans[maxn];

long long solve(int from, int to)
{
    for (int i = 1; i <= n; ++i)
    {
        ans[i] = -inf;
    }

    priority_queue<pair<long long, int>> pq;
    pq.push(make_pair(dist[from], from));

    ans[from] = dist[from];

    while (!pq.empty())
    {
        int node = pq.top().second;
        long long curr = pq.top().first;
        pq.pop();

        for (int i = 0; i < g[node].size(); ++i)
        {
            long long path = min(curr, dist[g[node][i].first]);

            if (ans[g[node][i].first] < path)
            {
                ans[g[node][i].first] = path;
                pq.push(make_pair(path, g[node][i].first));
            }
        }
    }

    return ans[to];
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;

        g[x].push_back(make_pair(y, w));
        g[y].push_back(make_pair(x, w));
    }

    cin >> k;

    for (int i = 1; i <= k; ++i)
    {
        cin >> startCities[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        dist[i] = inf;
    }

    priority_queue<pair<long long, int>> pq;

    for (int i = 1; i <= k; ++i)
    {
        pq.push(make_pair(0, startCities[i]));
        dist[startCities[i]] = 0;
    }

    while (!pq.empty())
    {
        int node = pq.top().second;
        long long curr = -pq.top().first;
        pq.pop();

        for (int i = 0; i < g[node].size(); ++i)
        {
            long long path = g[node][i].second + curr;
            int to = g[node][i].first;

            if (dist[to] > path)
            {
                dist[to] = path;
                pq.push(make_pair(-path, to));
            }
        }
    }

    cin >> q;

    for (int i = 1; i <= q; ++i)
    {
        int from, to;
        cin >> from >> to;
        cout << solve(from, to) << "\n";
    }

    return 0;
}

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message (stderr)

plan.cpp: In function 'long long int solve(int, int)':
plan.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~

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