[백준/C++] 최소비용 구하기 2

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 예전에 풀었던, 최단거리 알고리즘과 같은 문제다.

그래서 N이 1000이고 E가 100,000이므로 우선순위 queue를 이용한 dijikstra로 문제를 풀었다.

 

들어온 경로들로 graph를 만들고, 시작점부터 시작해 위치, 비용의 정보를 가진 pair를 priority queue에 넣는다.

이후 가장 비용이 적은 위치의 값을 가져와 다시 pq에 넣는 과정을 반복하면 된다.

여기서 최소 비용과 어느 도시에서 왔는지 정보를 저장할 visited라는 이름의  vector<pair<int,int>> 를 만들어 관리한다.

 

이후 pq에서 도시를 뽑으면 그 도시를 방문하는데 드는 비용을 visited에 저장된 비용과 같은지 비교한다.

만약 같지 않다면, 최소값이 아니라는 뜻이므로, 탐색할 필요가 없다.

 

도착점까지 도달하는 비용을 전부 구해 비교했다면, visited에 저장된 경로를 따라 역으로 어떤 경로를 통해 왔는지 구하면 된다.

 

 

​

[아이디어 정리]

1. 우선순위 queue를 이용한 Dijikstra 알고리즘으로 문제를 푼다.
2. 특정 도시에 방문하는 최소 비용을 갱신할 때 마다 어느 도시에서 왔는지 정보를 저장한다.
3. 모든 탐색이 끝났다면, 역으로 탐색을 시작해 어느 도시를 거쳐왔는지 경로를 구한다.
4. 최소비용과 도시의 개수 거쳐온 경로를 차례대로 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;

struct cmp {
	bool operator()(pair<int,int> a, pair<int,int>b)
	{
		return a.second > b.second;
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int,int>>> graph(n + 1); // 위치, 비용
	int a,b,c;

	for (int i=0; i<m; i++)
	{
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
	}
	priority_queue<pair<int, int>,vector<pair<int,int>>, cmp> pq;
	vector<pair<int, int>>visited(n + 1,make_pair(-1, 100000000)); //전 위치, 비용
	cin >> a >> b;
	pair<int, int>np = make_pair(a,0);
	pq.push(np);
	pair<int, int>tmp;
	while(!pq.empty())
	{
		np = pq.top();
		pq.pop();
		if (np.second>visited[np.first].second) {
			continue;
		}
		for (int i=0; i<graph[np.first].size(); i++)
		{
			tmp = graph[np.first][i];
			if (np.second+tmp.second< visited[tmp.first].second)
			{
				visited[tmp.first].first = np.first;
				visited[tmp.first].second = np.second + tmp.second;
				if (tmp.first==b)
				{
					continue;
				}
				pq.push(make_pair(tmp.first, visited[tmp.first].second));
			}
		}
	}
	cout << visited[b].second << "\n";
	stack<int>st;
	st.push(b);
	while(b!=a)
	{
		b = visited[b].first;
		st.push(b);
	}
	cout << st.size()<< "\n";
	while (!st.empty()) {
		cout << st.top() << " ";
		st.pop();
	}

	return 0;
}

 

---

중간에 가지치기를 하지 않아 시간초과가 처음에 났다.

오랜만에 Prioirty_queue를 사용했더니 손에 안익어서 약간 헷갈릴 뻔 했다;;

다시 슬슬 문제 푸는 연습을 시작해야할 것 같다;

 

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