백준16118 달빛 여우

작성일 | In

문제 링크

  • http://icpc.me/16118

문제 출처

  • 2018년 서울대학교 프로그래밍 경시대회 div.1 A번
  • 2018년 서울대학교 프로그래밍 경시대회 div.2 H번

사용 알고리즘

  • 다익스트라 알고리즘

시간복잡도

  • O(M log N)

풀이

보자마자 최단 경로 문제인 것을 알 수 있습니다.
다익스트라를 “적당히” 돌려줘서 최단 경로를 찾아주면 됩니다.

여우는 그냥 다익스트라 한 번 돌리면 끝나기 때문에 설명을 생략합니다.
늑대는 처음에는 빠르게, 그 다음에는 느리게 달리는 것을 반복합니다.
그래서 한 개의 노드를 fastNode/slowNode로 나누어서 그래프를 새로 만든 뒤 다익스트라를 돌립니다.
n번째 노드의 fastNode는 2n, slowNode는 2n+1로 정했습니다.
새로 만든 그래프에서 다익스트라를 돌린 뒤, 여우의 결과와 비교 후 답을 구하면 됩니다.

전체 코드

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
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, double> p1; //graph
typedef pair<double, int> p2; //pq

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

void make_graph(vector<p1> *prv, vector<p1> *nxt, int n){
	for(int i=1; i<=n; i++){
		for(int j=0; j<prv[i].size(); j++){
			auto now = prv[i][j];
			nxt[2*i].push_back({now.first*2+1, now.second/2});
			nxt[2*i+1].push_back({now.first*2, now.second*2});
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	vector<p1> g[10000], g1[10000];

	for(int i=0; i<m; i++){
		int a, b, c; cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}

	make_graph(g, g1, n); //fast:2n		slow:2n+1

	auto d1 = dijkstra(g, n, 1);
	auto tmp = dijkstra(g1, n*2, 2);
	vector<double> d2(n+1);
	for(int i=1; i<=n; i++){
		if(tmp[i*2] == 0 || tmp[i*2] == 1e9+7) d2[i] = tmp[i*2+1];
		else if(tmp[i*2+1] == 0 || tmp[i*2+1] == 1e9+7) d2[i] = tmp[i*2];
		else d2[i] = min(tmp[i*2], tmp[i*2+1]);
	}

	int cnt = 0;
	for(int i=2; i<=n; i++){
		if(d1[i] < d2[i]) cnt++;
	}
	cout << cnt;
}