oj.uz

Submission #124588

# Submission time Handle Problem Language Result Execution time Memory
124588 2019-07-03T14:37:17 Z MoNsTeR_CuBe Sightseeing (NOI14_sightseeing) C++17
15 / 25
 3500 ms 102640 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = numeric_limits<int>::max();

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, q;
	cin >> n >> m >> q;
	
	vector< vector< pair<int, int> > > Graph(n+1);
	
	for(int i = 0; i < m; 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(n+1, -INF);
	
	priority_queue< pair<int, int> > pq;
	
	dist[1] = INF;
	pq.push(make_pair(INF,1));
	
	while(!pq.empty()){
		pair<int, int> pair = pq.top();
		pq.pop();
		
		int node = pair.second;
		int cost = pair.first;
		
		if(cost < dist[node]) continue;
		
		for(int i = 0; i < (int)Graph[node].size(); i++){
			int to = Graph[node][i].first;
			int price = Graph[node][i].second;
			
			if(min(cost, price) > dist[to]){
				dist[to] = min(cost, price);
				pq.push(make_pair(dist[to], to));
			}
		}
	}
	
	for(int i = 0; i < q; i++){
		int a;
		cin >> a;
		cout << dist[a] << endl;
	}
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3420 KB Output is correct
2 Correct 50 ms 2936 KB Output is correct

Subtask #4
0 / 10.0

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