oj.uz

Submission #14636

# Submission time Handle Problem Language Result Execution time Memory
14636 2015-05-24T06:05:33 Z nosiar Sightseeing (NOI14_sightseeing) C++14
15 / 25
 3259 ms 173056 KB 
#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 } });
            }
        }
    }
    if (v <= 50000)
    for (int i = 0; i < q; ++i)
    {
        int x; cin >> x;
        cout << ans[x - 1] << endl;
    }
}}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15388 KB Output is correct
2 Correct 0 ms 15388 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15672 KB Output is correct
2 Correct 0 ms 15520 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 17812 KB Output is correct
2 Correct 188 ms 17196 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3259 ms 173056 KB Output isn't correct
2 Halted 0 ms 0 KB -