백준10715 JOI 공원

작성일 | In

문제 링크

  • http://icpc.me/10715

문제 출처

  • 2015 JOI 3번

사용 알고리즘

  • Dijkstra

시간복잡도

  • O(E log V)

풀이

광장 u까지의 거리가 dist[u]고, u 를 거쳐서 가는 가장 가까운 광장이 v, v까지의 거리가 dist[v]라고 합시다.
dist[u]와 dist[v] 사이에 있는 값으로 X를 잡으면 철거하는 도로는 늘어나지 않았는데 비용만 늘었으니까 항상 X = dist[u]일 때보다 손해 입니다.

다익스트라를 돌리면서 정점 u를 볼 때, X = dist[u]라면 공사 비용 = C * dist[u] + 철거하지 않은 간선 입니다.
철거하는 간선들은 지금까지 방문한 정점들 사이에 놓인 간선들입니다.
모든 간선 거리의 합을 구해두고, 공사 비용을 구하기 전에, 인접한 간선들을 순회해서 방문한 정점이 나온다면 그 간선의 거리를 빼주고 공사 비용을 계산하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

vector<p> g[101010];
int n, m, c;
ll dist[101010];
int chk[101010];
ll sum;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> c;
	for(int i=0; i<m; i++){
		int s, e, x; cin >> s >> e >> x;
		g[s].push_back({e, x});
		g[e].push_back({s, x});
		sum += x;
	}

	memset(dist, 0x3f, sizeof dist);
	ll ans = sum;
	priority_queue<p> pq; pq.push({0, 1}); dist[1] = 0;
	while(pq.size()){
		int now = pq.top().second;
		ll cost = -pq.top().first;
		pq.pop();
		if(chk[now]) continue;
		if(dist[now] < cost) continue;
		chk[now] = 1;
		for(auto i : g[now]){
			int nxt = i.first;
			ll nxtCost = i.second;
			if(chk[nxt]) sum -= nxtCost;
		}
		ans = min(ans, cost*c + sum);

		for(auto i : g[now]){
			int nxt = i.first;
			ll nxtCost = cost + i.second;
			if(dist[nxt] > nxtCost){
				dist[nxt] = nxtCost;
				pq.push({-nxtCost, nxt});
			}
		}
	}
	cout << ans;
}