oj.uz

답안 #652829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652829 2022-10-24T17:33:16 Z red24 관광 (NOI14_sightseeing) C++14
25 / 25
 3056 ms 166128 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define mp make_pair
#define vi vector<int>
#define pi pair<int ,int>
#define vpi vector<pair<int, int>>
#define vvi vector<vector<int>>
#define pqd priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
const int mod = 1e9+7;
#define ll long long

//PROGRAM

int main(){
	// fastio
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// fastio
	
	int n, e, q; cin >> n >> e >> q;
	vpi a[n+1];
	for (int i = 1; i <= e; i++)
	{
		int x, y, c; cin >> x >> y >> c;
		a[x].pb({y, c});
		a[y].pb({x, c});
	}

	priority_queue<pi, vpi> pq;
	vi d(n+1, -1);
	vi vis(n+1);
	
	int s = 1; // 1 is the source
	
	pq.push(mp(0, s));	// push source in the queue
	d[1] = 0;
	while(!pq.empty())
	{
		pi c = pq.top(); pq.pop();
		if (vis[c.second]) continue;
		vis[c.second] = true;
		for (auto x : a[c.second])
		{
			if (vis[x.first]) continue;
			if (c.second == 1)
			{
				d[x.first] = x.second;
				pq.push({x.second, x.first});
				continue;
			}
			if (min(c.first, x.second) > d[x.first])
			{
				d[x.first] = min(c.first, x.second);
				pq.push({d[x.first], x.first});
			}
		}
	}
	
	while(q--)
	{
		int x; cin >> x;
		cout << d[x] << '\n';
	}
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
10.0 / 10.0

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