oj.uz

답안 #103439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103439 2019-03-30T17:39:09 Z SecretAgent007 관광 (NOI14_sightseeing) C++17
15 / 25
 3500 ms 188456 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

const int INF = 9223372036854775807;

vector< vector< pair< int, int > > > Graph;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int v, e, q;
    cin >> v >> e >> q;

    Graph.resize(v+1);

    for(int i = 0; i < e ; i++){
        int a, b, c;
        cin >> a >> b >> c;
        Graph[a].push_back(make_pair(b,c));
        Graph[b].push_back(make_pair(a,c));
    }

    vector< int > dist(v+1,-INF);

    priority_queue< pair<int, int> > pq;

    pq.push(make_pair(INF,1));

    while(!pq.empty()){

        pair<int, int> p = pq.top();

        int a = p.first;
        int b = p.second;

        pq.pop();

        if(dist[b] > a) continue;

        for(auto c : Graph[b]){
            if(dist[c.first] < min(a,c.second)){
                dist[c.first] = min(a,c.second);
                pq.push(make_pair(dist[c.first],c.first));
            }
        }
    }

    while(q--){
        int a;
        cin >> a;
        cout << dist[a] << '\n';
    }
}
/*
4 4 2
1 2 10
1 3 30
2 4 20
3 4 5
3
4
*/

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 4576 KB Output is correct
2 Correct 47 ms 4616 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3596 ms 188456 KB Time limit exceeded
2 Halted 0 ms 0 KB -