백준 Gold 1 달빛 여우

달빛 여우 (백준 Gold 1)

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

n개의 그루터기와 m개의 오솔길이 존재하고
오솔길은 다음과 같은 정보를 가진다

• a,b,c
  
  • a : 시작 그루터기
    
  • b : 도착 그루터기
    
  • c : 그루터기 간 거리
    

여우와 늑대의 달리기 방식을 고려하여
여우가 더 빨리 도착할 수 있는 그루터기의 개수를 구하는 방식

유의할 점

• 두 동물 모두 1번 그루터기에서 시작
  
• 중복된 오솔길이 등장하지 않음
  
• 두 동물의 달리는 방식이 다름
  
  • 여우는 늘 일정한 속도로 달림
    
  • 늑대는 시작시 2배의 속도로 달릴 수 있으나
    다음 그루터기에 도착시엔 절반의 속도로 달려야 함
    

풀이 방법

조금 특이한 다익스트라 문제이다

• 1번에서 나머지 그루터기에 대한 최소 거리를 구하는 것이
  이 문제의 골자이다
  

• 여우의 달리는 방식은 일반적인 다익스트라를 통해 구할 수 있음!
  
  • pq 설정과 최단거리 갱신
    
• 늑대의 경우는 해당 방식에서 몇가지를 추가로 손보면 가능
  
  • ‘2배’로 달리는 경우 와 ‘절반’으로 달리는 경우에 대한 방문 배열 분리,
    마지막에 두 배열의 작은 값들만을 취함
    
    • 이래야 모든 그루터기의 최소 거리를 구할 수 있으므로
      
  • 부동 소수점을 통하여 .5초에 대한 차이점을 주어야 함
    (int는 버림 처리 하므로)
    
  • 이후 ‘해당 거리’에 대한 2배, 절반 처리를 진행
    (이전 값 전체가 아님에 유의할 것)
    

제출 코드

#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
#include<limits.h>

using namespace std;

typedef pair<int, int> pii;

struct infos
{
	int now;
	long double nowCost;
	bool doubleTime = false;
};

struct Compare
{
	bool operator()(infos& a, infos& b)
	{
		return a.nowCost > b.nowCost;
	}
};

void GetFoxV(unordered_map<int, vector<pii>>& maps, vector<long double>& foxVec)
{
	priority_queue<infos, vector<infos>, Compare> pq;
	pq.push({ 0,0,false });
	
	while (pq.empty() == false)
	{
		int now = pq.top().now;
		long double nowC = pq.top().nowCost;
		pq.pop();

		if (foxVec[now] <= nowC)
			continue;

		foxVec[now] = nowC;

		for (const pii& p : maps[now])
		{
			pq.push({ p.first,p.second + nowC,false });
		}
	}
}

void GetWolfV(unordered_map<int, vector<pii>>& maps, vector<long double>& wolfVec)
{
	priority_queue<infos, vector<infos>, Compare> pq;
	pq.push({ 0,0,false });

	int n = wolfVec.size();

	vector<long double> av(n, INT_MAX);
	vector<long double> bv(n, INT_MAX);

	while (pq.empty() == false)
	{
		int now = pq.top().now;
		long double nowC = pq.top().nowCost;
		bool bDouble = pq.top().doubleTime;
		pq.pop();

		if (bDouble)
		{
			if (av[now] <= nowC)
				continue;

			av[now] = nowC;
		}
		else
		{
			if (bv[now] <= nowC)
				continue;

			bv[now] = nowC;
		}

		for (const pii& p : maps[now])
		{
			if (bDouble)
			{
				pq.push({ p.first,(p.second) * 2 + nowC,false });
			}
			else
			{
				pq.push({ p.first,(p.second) / 2.0 + nowC,true });
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		if (av[i] < bv[i])
			wolfVec[i] = av[i];
		else
			wolfVec[i] = bv[i];
	}

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	unordered_map<int, vector<pii>> maps;

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		a--;
		b--;
		maps[a].push_back({ b,c });
		maps[b].push_back({ a,c });
	}

	vector<long double> foxValues(n, INT_MAX);
	vector<long double> wolfValues(n, INT_MAX);

	GetFoxV(maps, foxValues);
	GetWolfV(maps, wolfValues);

	int ret = 0;

	for (int i = 1; i < n; i++)
	{
		if (foxValues[i] < wolfValues[i])
			ret++;
	}

	cout << ret;

	return 0;
}

결과

골드 1이라서 조금 긴장하였지만 단계를 나누어 풀 수 있었던 문제이다