알고리즘/PS

[C++] 백준 16118 : 달빛 여우

BigmacGood 2022. 7. 12. 23:02

https://www.acmicpc.net/problem/16118

 

16118번: 달빛 여우

첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b

www.acmicpc.net

백준 16118번 달빛 여우 문제를 풀었다.

 

시작 노드에서 다른 노드까지의 최단 비용을 구하고, 간선의 가중치가 양수라서 다익스트라를 사용했다.

여우는 모든 노드를 같은 속도로 이동한다.

늑대는 2배 빠르게 이동했다가 1/2배 느리게 이동하는 것을 반복한다.

 

여우의 속도를 2로 두고

늑대가 빠르게 이동할 때는 1, 느리게 이동할 때는 4의 속도로 두었다.

 

노드에 turn 변수를 만들어서 늑대의 속도를 결정했다.

 

여우는 일반적인 다익스트라를 사용해서 최단 비용을 구했다.

늑대는 dist 배열에 한 차원 더해서 사용했다.

dist[0][x] : 늑대가 x노드에 느리게 들어올 때의 최단 비용을 저장

dist[1][x] : 늑대가 x노드에 빠르게 들어올 때의 최단 비용을 저장

 

이렇게 두 개로 나눠서 저장해야 최단 비용을 제대로 구할 수 있다.

예를 들어 입력 값이 아래와 같다면  2번 노드에서 3번 노드로 갈 때 빠르게 가야 최단 비용을 구할 수 있다.

5 5

1 2 1

1 4 5

1 5 3

4 5 4

2 3 400

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#pragma warning(disable:4996)

using namespace std;

#define INF 1000000000
#define LLINF 9223372036854775800

struct Node {
	int end;
	int cost;
	int turn;
};

struct compare {
	bool operator()(Node a, Node b) {
		return a.cost > b.cost;
	}
};

int n, m;
vector<Node> v[4001];

int Dijkstra(int dest) {
	priority_queue < Node, vector<Node>, compare> pq;
	vector<int> dist_fox;
	dist_fox.assign(n + 1, INF);
	dist_fox[1] = 0;
	pq.push({ 1,dist_fox[1],0 });

	while (!pq.empty()) {
		Node temp = pq.top();
		int cur = temp.end;
		int cost = temp.cost;
		int turn = temp.turn;
		pq.pop();

		if (dist_fox[cur] < cost)
			continue;

		for (int i = 0; i < v[cur].size(); i++) {
			temp = v[cur][i];
			int next = temp.end;
			int next_cost = cost + temp.cost * 2;
			int next_turn = turn + 1;
			if (dist_fox[next] > next_cost) {
				dist_fox[next] = next_cost;
				pq.push({ next,next_cost,next_turn });
			}
		}
	}


	vector<int> dist_wolf[2];
	dist_wolf[0].assign(n + 1, INF);
	dist_wolf[1].assign(n + 1, INF);
	dist_wolf[0][1] = 0;
	pq.push({ 1,dist_wolf[0][1],0});

	while (!pq.empty()) {
		Node temp = pq.top();
		int cur = temp.end;
		int cost = temp.cost;
		int turn = temp.turn;
		pq.pop();

		if (dist_wolf[turn%2][cur] < cost)
			continue;

		for (int i = 0; i < v[cur].size(); i++) {
			temp = v[cur][i];
			int next = temp.end;
			int next_cost = temp.cost;
			int next_turn = turn + 1;

			if (turn % 2 == 0) {
				next_cost = cost + next_cost;
				if (dist_wolf[1][next] > next_cost) {
					dist_wolf[1][next] = next_cost;
					pq.push({ next,next_cost,next_turn });
				}
			}
			else {
				next_cost = cost + next_cost * 4;
				if (dist_wolf[0][next] > next_cost) {
					dist_wolf[0][next] = next_cost;
					pq.push({ next,next_cost,next_turn });
				}
			}
		}
	}

	int ans = 0;
	for (int i = 2; i <= n; i++) {
		if (dist_fox[i] < min(dist_wolf[0][i],dist_wolf[1][i]))
			ans++;
	}

	return ans;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int start, end, cost;
		scanf("%d %d %d", &start, &end, &cost);
		v[start].push_back({ end,cost,0 });
		v[end].push_back({ start,cost,0 });
	}

	int ans = Dijkstra(n);

	cout << ans;

	return 0;
}

 

'알고리즘 > PS' 카테고리의 다른 글

[C++] 백준 1486 : 등산  (0) 2022.07.12
[C++] 백준 1584 : 게임  (0) 2022.07.12
[C++] 백준 10423 : 전기가 부족해  (0) 2022.07.10
[C++] 백준 12100 : 2048 (Easy)  (0) 2022.07.10
[C++] 백준 1162 : 도로포장  (0) 2022.07.10