[백준] 16118 달빛 여우

문제

관악산 기슭에는 보름달을 기다리는 달빛 여우가 한 마리 살고 있다. 달빛 여우가 보름달의 달빛을 받으면 아름다운 구미호로 변신할 수 있다. 하지만 보름달을 기다리는 건 달빛 여우뿐만이 아니다. 달빛을 받아서 멋진 늑대인간이 되고 싶어 하는 달빛 늑대도 한 마리 살고 있다.

관악산에는 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인 오솔길이 나 있음을 의미한다.

출력

첫 줄에 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있는 나무 그루터기의 개수를 출력한다.

 

달빛여우가 1번부터 도착지점까지의 최단거리는 위의 그래프 그대로 다익스트라를 진행합니다.

 

하지만 달빛늑대는 weight가 2배, 1/2배 2배 1/2배.... 반복되기때문에

한 노드를 반으로 쪼개서 다익스트라를 진행하면 됩니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };

int N, M, d1[4001], v1[4001], v2[4001][2];
double d2[4001][2];
vector<pi> adj[4001];
void dij1(int s) {
	fill(d1, d1 + N + 1, 0x3f3f3f3f);
	d1[s] = 0;
	priority_queue<pi, vector<pi>, greater<pi>>pq;
	pq.push({ d1[s],s });
	while (!pq.empty()) {
		auto [dist, cur] = pq.top();
		pq.pop();
		if (v1[cur])continue;
		v1[cur] = 1;
		for (auto [next, cost] : adj[cur]) {
			if (d1[next] > d1[cur] + cost) {
				d1[next] = d1[cur] + cost;
				pq.push({ d1[next],next });
			}
		}
	}
}
struct node {
	double dist;
	int cur;
	bool s;
	
	bool operator<(const node& d) const {
		return dist > d.dist;
	}
};
void dij2(int s) {
	REP(i, N) {
		rep(j, 2)d2[i][j] = 987654321;
	}
	d2[s][0] = 0;
	//d2[s][1] = 987654321;
	priority_queue<node>pq;
	pq.push({ d2[s][0], s, 0}); //0 : 2배로 나가야함 , 1: 1/2배로 나가야함
	while (!pq.empty()) {
		auto [dist, cur, s] = pq.top();
		pq.pop();
		if (v2[cur][s])continue;
		v2[cur][s] = 1;
		for (auto [next, cost] : adj[cur]) {
			if (s == 0) {
				if (d2[next][1] > d2[cur][0] + (double)cost / 2) {
					d2[next][1] = d2[cur][0] + (double)cost / 2;
					pq.push({d2[next][1], next, 1});
				}
			}
			else {
				if (d2[next][0] > d2[cur][1] + cost * 2) {
					d2[next][0] = d2[cur][1] + cost * 2;
					pq.push({ d2[next][0], next, 0 });
				}
			}
		}
	}
}
int main() {
	FAST;
	cin >> N >> M;
	while (M--) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ b,c });
		adj[b].push_back({ a,c });
	}
	dij1(1);
	dij2(1);
	int t = 0;
	for (int i = 2; i <= N; i++) {
		if (d1[i] < d2[i][0] && d1[i] < d2[i][1]) {
			t++;
		}
	}
	cout << t;
}