kunkunwoo@blog:~$ 거누권의 생각깜지

백준 10217번 _ KCM Travel

· 배운 것 · 10분 읽기

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

10217번: KCM Travel

조건

1) 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길
2) 공항의 수 N (2 ≤ N ≤ 100), 총 지원비용 M (0 ≤ M ≤ 10,000), 티켓정보의 수 K (0 ≤ K ≤ 10,000)

1. 풀이방법

1) 최단 경로를 찾는다 -> 다익스트라, 벨만 포드, BFS, 플로이드 와샬
2) 가중치는 1이 아니고 인천( 1번 노드 )에서 LA( N번 노드)로 가야한다. -> 다익스트라, 벨만 포드
3) 가중치중에 음의 값은 없다 -> 다익스트라

다익스트라 알고리즘을 쓰는 것은 정해졌다. 하지만 일반적인 다익스트라문제보다 조건이 하나 더 늘었다.
( M원 이하로 사용 )

그러므로 일반적으로 쓰던
특정노드에서의 최소거리 배열 dist[정점] - > dist[정점][비용]
이렇게 바꾸어 dp방식을 이용하여 풀이한다.

//갱신됬으면 prique 에 넣기
			if (dist[there][nextcost] > nextdis)
			{
				//불필요한 값들이 나오는것을 막기위해서 다 바꿔줌
				for (int p = nextcost; p <= m; p++)
				{
					if (dist[there][p] > nextdis)
						dist[there][p] = nextdis;
				}
				que.push({ -nextcost, {there, nextdis} });
			}

또, 중요한 사항은 중간 중간 주어진 비용보다 높을때라던가, 이미 dist[정점][비용]에 더 낮은 값이 들어가 있는 경우를 가지치기 해주어야 시간내에 들어올수 있다.

2. 코드

첫번째 통과 코드 ( 다익스트라를 반복문으로 구현 )

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define LIMIT 987654321

using namespace std;

class info
{
public:
	int v;
	int cost;
	int distance;
	info(int v_in, int cost_in, int distance_in)
		:v(v_in), cost(cost_in), distance(distance_in)
	{}
};

struct cmp {
	bool operator()(const info& a, const info& b) {
		return a.cost < b.cost;
	}
};

int dist[102][10002];
vector<vector<info>>edge;
int n, m, k;

void edgeClear()
{
	for (int i = 1; i <= n; i++)
		edge[i].clear();
}

void distInit()
{
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= m; j++)
			dist[i][j] = LIMIT;
	dist[1][0] = 0;
}

void dijkstra(int here, int cost, int distance)
{
	//dist 초기화
	distInit();

	priority_queue<pair<int,pair<int,int>>> que;
	que.push({cost ,{here, distance} });

	while (!que.empty())
	{
		int there = que.top().second.first;
		int nextcost = -que.top().first;
		int nextdis = que.top().second.second;
		here = there;
		cost = nextcost;
		distance = nextdis;
		que.pop();

		for (int i = 0; i < (int)edge[here].size(); i++)
		{
			int there = edge[here][i].v;
			int nextcost = edge[here][i].cost + cost;
			int nextdis = edge[here][i].distance + distance;

			//최대 비용을 초과할시 패스
			if (nextcost > m)
				continue;

			//갱신됬으면 prique 에 넣기
			if (dist[there][nextcost] > nextdis)
			{
				//불필요한 값들이 나오는것을 막기위해서 다 바꿔줌
				for (int p = nextcost; p <= m; p++)
				{
					if (dist[there][p] > nextdis)
						dist[there][p] = nextdis;
				}
				que.push({ -nextcost, {there, nextdis} });
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int test;
	cin >> test;
	edge.resize(102);
	for (int i = 0; i < test; i++)
	{
		cin >> n >> m >> k;

		int u, v, c, d;
		for (int j = 0; j < k; j++)
		{
			cin >> u >> v >> c >> d;
			edge[u].push_back(info(v, c, d));
		}

		//dijstra
		dijkstra(1, 0, 0);

		int answer = dist[n][m];
	
		if (answer == LIMIT)
			cout << "Poor KCM" << '\n';
		else
			cout << answer << '\n';

		//edge clear
		edgeClear();
	}
	return 0;
}

두번째 통과 코드 ( 다익스트라를 재귀함수로 구현 )

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define LIMIT 987654321

using namespace std;

class info
{
public:
	int v;
	int cost;
	int distance;
	info(int v_in, int cost_in, int distance_in)
		:v(v_in), cost(cost_in), distance(distance_in)
	{}
};

struct cmp {
	bool operator()(const info& a, const info& b) {
		return a.cost < b.cost;
	}
};

int dist[102][10002];
vector<vector<info>>edge;
int n, m, k;

void edgeClear()
{
	for (int i = 1; i <= n; i++)
		edge[i].clear();
}

void distInit()
{
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= m; j++)
			dist[i][j] = LIMIT;
	dist[1][0] = 0;
}

priority_queue<pair<int, pair<int, int>>> que;
void dijkstra(int here, int cost, int distance)
{
	for (int i = 0; i < (int)edge[here].size(); i++)
	{
		int there = edge[here][i].v;
		int nextcost = edge[here][i].cost + cost;
		int nextdis = edge[here][i].distance + distance;

		//최대 비용을 초과할시 패스
		if (nextcost > m)
			continue;

		//갱신됬으면 prique 에 넣기
		if (dist[there][nextcost] > nextdis)
		{
			//불필요한 값들이 나오는것을 막기위해서 다 바꿔줌
			for (int p = nextcost; p <= m; p++)
			{
				if (dist[there][p] > nextdis)
					dist[there][p] = nextdis;
			}
			que.push({ -nextcost, {there, nextdis} });
		}
	}

	//다음 정점으로 ㄱㄱ
	if (!que.empty())
	{
		int there = que.top().second.first;
		int nextcost = -que.top().first;
		int nextdis = que.top().second.second;
		que.pop();
		dijkstra(there, nextcost, nextdis);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int test;
	cin >> test;
	edge.resize(102);
	for (int i = 0; i < test; i++)
	{
		cin >> n >> m >> k;
		//dist 초기화
		distInit();
		int u, v, c, d;
		for (int j = 0; j < k; j++)
		{
			cin >> u >> v >> c >> d;
			edge[u].push_back(info(v, c, d));
		}

		//dijstra
		dijkstra(1, 0, 0);

		int answer = dist[n][m];

		if (answer == LIMIT)
			cout << "Poor KCM" << '\n';
		else
			cout << answer << '\n';

		//edge clear
		edgeClear();
	}
	return 0;
}

3. 후기

비교함수 잘못짜서 개고생했다.. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ