백준12834 주간 미팅

작성일 | In

문제 링크

  • http://icpc.me/12844

사용 알고리즘

  • Dijkstra

시간복잡도

  • O(E log V)

풀이

KIST를 시작점으로 잡아서 다익스트라를 돌리고, 씨알 푸드를 시작점으로 잡아서 한 번 더 다익스트라를 돌리면 쉽게 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

int n, v, e, a, b;
vector<int> home;
vector<p> g[1010];

vector<int> kist, cr;

void dijkstra(vector<int> &dist, int s){
	dist = vector<int>(v+1, 1e9+7);
	priority_queue<p> pq; pq.push({0, s});
	dist[s] = 0;
	while(!pq.empty()){
		int now = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if(cost > dist[now]) continue;
		for(auto i : g[now]){
			int nxt = i.first;
			int nxtCost = cost + i.second;
			if(dist[nxt] > nxtCost){
				dist[nxt] = nxtCost;
				pq.push({-nxtCost, nxt});
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> v >> e >> a >> b; home.resize(n);
	for(int i=0; i<n; i++) cin >> home[i];

	for(int i=0; i<e; i++){
		int ss, ee, xx; cin >> ss >> ee >> xx;
		g[ss].push_back({ee, xx});
		g[ee].push_back({ss, xx});
	}

	dijkstra(kist, a);
	dijkstra(cr, b);

	long long ans = 0;
	for(auto i : home){
		long long di = 0;
		if(kist[i] > 1e9) di--;
		else di += kist[i];
		if(cr[i] > 1e9) di--;
		else di += cr[i];
		ans += di;
	}
	cout << ans;
}