| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 2436 | 513 | 347 | 21.499% |
문제
관악산 기슭에는 보름달을 기다리는 달빛 여우가 한 마리 살고 있다. 달빛 여우가 보름달의 달빛을 받으면 아름다운 구미호로 변신할 수 있다. 하지만 보름달을 기다리는 건 달빛 여우뿐만이 아니다. 달빛을 받아서 멋진 늑대인간이 되고 싶어 하는 달빛 늑대도 한 마리 살고 있다.
관악산에는 1번부터 N번까지의 번호가 붙은 N개의 나무 그루터기가 있고, 그루터기들 사이에는 M개의 오솔길이 나 있다. 오솔길은 어떤 방향으로든 지나갈 수 있으며, 어떤 두 그루터기 사이에 두 개 이상의 오솔길이 나 있는 경우는 없다. 달빛 여우와 달빛 늑대는 1번 나무 그루터기에서 살고 있다.
보름달이 뜨면 나무 그루터기들 중 하나가 달빛을 받아 밝게 빛나게 된다. 그러면 달빛 여우와 달빛 늑대는 먼저 달빛을 독차지하기 위해 최대한 빨리 오솔길을 따라서 그 그루터기로 달려가야 한다. 이때 달빛 여우는 늘 일정한 속도로 달려가는 반면, 달빛 늑대는 달빛 여우보다 더 빠르게 달릴 수 있지만 체력이 부족하기 때문에 다른 전략을 사용한다. 달빛 늑대는 출발할 때 오솔길 하나를 달빛 여우의 두 배의 속도로 달려가고, 그 뒤로는 오솔길 하나를 달빛 여우의 절반의 속도로 걸어가며 체력을 회복하고 나서 다음 오솔길을 다시 달빛 여우의 두 배의 속도로 달려가는 것을 반복한다. 달빛 여우와 달빛 늑대는 각자 가장 빠르게 달빛이 비치는 그루터기까지 다다를 수 있는 경로로 이동한다. 따라서 둘의 이동 경로가 서로 다를 수도 있다.
출제자는 관악산의 모든 동물을 사랑하지만, 이번에는 달빛 여우를 조금 더 사랑해 주기로 했다. 그래서 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있는 그루터기에 달빛을 비춰 주려고 한다. 이런 그루터기가 몇 개나 있는지 알아보자.
입력
첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다.
두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b, 1 ≤ d ≤ 100,000)가 주어진다. 이는 a번 그루터기와 b번 그루터기 사이에 길이가 d인 오솔길이 나 있음을 의미한다.
출력
첫 줄에 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있는 나무 그루터기의 개수를 출력한다.
접근
여우같은 경우는 일반적으로 다익스트라로 풀면 된다.
늑대는 두가지 상태가 존재하므로, 거리 테이블에 2 크기 차원을 추가한다.
그리고 동일하게 다익스트라로 풀되, 다음 거리를 *2 혹은 /2 연산을 해주면 된다.
실수 처리는 귀찮기에 모든 edge의 거리에 *2 전처리를 해주었다.
풀이
wolf는 pq에 추가적으로 idx가 들어간 것을 확인할 수 있다.
이것이 1이면 nd에 *2, 0이면 /2 연산을 추가해주었다.
두 번의 BFS가 끝나면 fox[i]가 wolf[i][0 ~ 1]중 더 작은 것을 카운팅한다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, M, fox[4001], wolf[4001][2], a, b, d, ans = 0;
vector<pair<int, int>> edge[4001];
void fBFS()
{
fox[1] = 0;
priority_queue<pair<int, int>> pq;
pq.push({ 0, 1 });
while (!pq.empty())
{
int dist = -pq.top().first;
int node = pq.top().second;
pq.pop();
if (dist > fox[node]) continue;
for (auto p : edge[node])
{
int next = p.first;
int nd = p.second;
if (fox[next] > dist + nd)
{
fox[next] = dist + nd;
pq.push({ -fox[next], next });
}
}
}
}
void wBFS()
{
wolf[1][1] = 0;
priority_queue<pair<int, pair<int, int>>> pq;
pq.push({ 0, {1, 1} });
while (!pq.empty())
{
int dist = -pq.top().first;
int node = pq.top().second.first;
int idx = pq.top().second.second;
pq.pop();
if (dist > wolf[node][idx]) continue;
int ni = idx ^ 1;
{
for (auto p : edge[node])
{
int next = p.first;
int nd = idx ? p.second / 2 : p.second * 2;
if (wolf[next][ni] > dist + nd)
{
wolf[next][ni] = dist + nd;
pq.push({ -wolf[next][ni], {next, ni} });
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN2(N, M);
FUP(i, 1, N) fox[i] = wolf[i][0] = wolf[i][1] = INT_MAX;
while (M--)
{
CIN3(a, b, d);
edge[a].push_back({ b, 2 * d });
edge[b].push_back({ a, 2 * d });
}
fBFS();
wBFS();
FUP(i, 2, N)
{
if (fox[i] < min(wolf[i][1], wolf[i][0])) ans++;
}
COUT(ans);
return 0;
}