oj.uz

Submission #8128

# Submission time Handle Problem Language Result Execution time Memory
8128 2014-08-31T05:19:27 Z baneling100 Sightseeing (NOI14_sightseeing) C++
15 / 25
 3500 ms 165568 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 0x7fffffff

using namespace std;

typedef pair <int,int> ppair;
priority_queue <ppair> MaxQ;
vector <ppair> A[500001];
int V, E, Q, X[500000], D[500001], Check[500001];

void input(void) {

    int i, v1, v2, q;

    scanf("%d %d %d",&V,&E,&Q);
    for(i=1 ; i<=E ; i++) {
        scanf("%d %d %d",&v1,&v2,&q);
        A[v1].push_back(make_pair(v2,q));
        A[v2].push_back(make_pair(v1,q));
    }
    for(i=1 ; i<=Q ; i++)
        scanf("%d",&X[i]);
}

void process(void) {

    int i, j, Now, Value;

    for(i=2 ; i<=V ; i++)
        D[i]=-1;
    D[1]=INF;
    MaxQ.push(make_pair(D[1],1));
    while(!MaxQ.empty()) {
        Now=MaxQ.top().second;
        MaxQ.pop();
        if(Check[Now])
            continue;
        Check[Now]=1;
        j=A[Now].size();
        for(i=0 ; i<j ; i++) {
            Value=min(D[Now],A[Now][i].second);
            if(D[A[Now][i].first]<Value) {
                D[A[Now][i].first]=Value;
                MaxQ.push(make_pair(Value,A[Now][i].first));
            }
        }
    }
}

void output(void) {

    int i;

    for(i=1 ; i<=Q ; i++)
        printf("%d\n",D[X[i]]);
}

int main(void) {

    input();
    process();
    output();

    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 20636 KB Output is correct
2 Correct 44 ms 20372 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2872 ms 114852 KB Output is correct
2 Execution timed out 3500 ms 165568 KB Program timed out