Submission #14638

#	Time	Username	Problem	Language	Result	Execution time	Memory
14638		nosiar	Sightseeing (NOI14_sightseeing)	C++14	15 / 25	3248 ms	173056 KiB

sightseeing

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <numeric>
#include <limits>

using namespace std;

int v, e, q;
vector<pair<int,int>> edge[500050];
int ans[500050];
int main() { 
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false); //int tests; cin >> tests; while (tests--)
{
    cin >> v >> e  >> q;
    for (int i = 0; i < e; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        edge[a].push_back({ c, b });
        edge[b].push_back({ c, a });
    }
    priority_queue<pair<int, pair<int, int>>> pq;
    for (auto e : edge[0])
    {
        pq.push({ e.first, { 0, e.second } });
    }
    memset(ans, -1, sizeof(ans));
    ans[0] = 987654321;
    while (!pq.empty())
    {
        auto e = pq.top(); pq.pop();
        if (ans[e.second.second] == -1)
        {
            ans[e.second.second] = min(ans[e.second.first], e.first);
            for (auto ee : edge[e.second.second])
            {
                if (ans[ee.second] == -1)
                    pq.push({ ee.first, { e.second.second, ee.second } });
            }
        }
    }
    for (int i = 0; i < q; ++i)
    {
        int x; cin >> x;
        if (v <= 50000)
            cout << ans[x - 1] << endl;
        else
            cout << ans[0];
    }
}}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 0 / 10