(백준/c++) 1753번 - 최단경로

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

 

	#include <iostream>
	#include <queue>
	#include <vector>
	using namespace std;
	#define max_vertex 20'001
	#define inf 10'000'000
	vector<pair<int, int>> vec[max_vertex];
	//vector<int> dir;
	int dist[max_vertex];
	void Dijkstra(int start)
	{
	dist[start] = 0;
	//d[start] = 0;
	// 0, INF, INF, INF, INF, INF .....
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	while (!pq.empty())
	{
	int distance = -pq.top().first; //2. 0 (거리)
	int start = pq.top().second; // 1. start
	pq.pop();
	if (dist[start] < distance) continue;
	for (int i = 0; i < vec[start].size(); i++)
	{
	int position = vec[start][i].first; // 어디가니?
	int nextdistance = vec[start][i].second + distance; // A - B - C
	if (dist[position] > nextdistance)
	{
	dist[position] = nextdistance;
	pq.push(make_pair(-nextdistance, position));
	}
	}
	}
	}
	int main(void)
	{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int V, E;
	cin >> V>> E;
	int start;
	cin >> start;
	for (int i = 1; i <= V; i++)
	{
	dist[i]=(inf);
	}
	for (int i = 0; i < E; i++)
	{
	int u, v, w;
	cin >> u >> v >> w;
	vec[u].push_back(make_pair(v, w));
	}
	Dijkstra(start);
	for (int i = 1; i <= V; i++)
	{
	if (dist[i] == inf)
	cout << "INF" << "\n";
	else
	cout << dist[i] << "\n";
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub

많이 틀렸던 이유 :

1. C++에서 std::pair는 first끼리를 먼저 비교하고, first가 같으면 second를 비교합니다. 이게 무슨 뜻이냐면, pair<int, int>로 우선순위 큐에 원소를 넣는다면 반드시 first에 거리가 들어가야 한다는 뜻입니다. 정점 번호끼리의 비교에는 아무런 의미가 없습니다. 물론 직접 비교 함수를 정의해서 second를 먼저 보게 만들 수는 있습니다.
2.  출처: www.acmicpc.net/board/view/34516