https://www.acmicpc.net/problem/16118
백준 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 |