oj.uz

Submission #122490

# Submission time Handle Problem Language Result Execution time Memory
122490 2019-06-28T12:26:52 Z kimbj0709 Sightseeing (NOI14_sightseeing) C++17
15 / 25
 3500 ms 160328 KB 
#include <bits/stdc++.h>
using namespace std;
int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
  int no_of_input;
  
  int no_of_edge,no_of_query;
  int input1,input2,input3;
  vector<int> visited(500000,-1);
  cin >> no_of_edge >> no_of_input >> no_of_query;
  vector<pair<int,int> > adj[no_of_edge+2];
  for(int i=0;i<no_of_input;i++){
    cin >> input1 >> input2 >> input3;
    adj[input1].push_back(make_pair(input2,input3));
    adj[input2].push_back(make_pair(input1,input3));
  }
  priority_queue<pair<int,int> > q1;//weight node
  q1.push(make_pair(2147483647,1));
  visited[1] = 2147483647;
  int minimum;
  while(q1.size()!=0){
    pair<int,int> a = q1.top();
    q1.pop();
    for(auto k:adj[a.second]){
      minimum = min(visited[a.second],k.second);
      if(visited[k.first]<minimum){
        visited[k.first] = minimum;
        q1.push(make_pair(minimum,k.first));
      }
    }
  }
  for(int i=0;i<no_of_query;i++){
    cin >> input1;
    cout << visited[input1] << "\n";
  }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 3 ms 2304 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2432 KB Output is correct
2 Correct 4 ms 2304 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6008 KB Output is correct
2 Correct 34 ms 5368 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3597 ms 160328 KB Time limit exceeded
2 Halted 0 ms 0 KB -