[C++] Dijkstra algorithm - 백준 1238번 파티

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

1238번: 파티

---

#include <bits/stdc++.h>
using namespace std;

int n, m, x;
// shortest length
int SL[1005];
// 돌아가는 길
int SB[1005];
int visited[1005];

class tpl {
public:
	// a에서 b로 가는 노드. 길이는 l
	int a, b, l;
};

class pkt {
public:
	// a에서 b로 가는데 길이가 l
	int a, b, l, cnt;

};

vector<tpl> ED[1005];

struct comp {
	// l 기준 오름차순으로 설정.
	bool operator()(pkt A, pkt B) {
		if (A.l > B.l)
			return true;
		return false;
	}
};

priority_queue<pkt, vector<pkt>, comp> pq;

void dijk(int s)
{
	pkt p, q;  int i;
	p.a = 0; p.b = s; p.l = 0;
	pq.push(p);

	while (!pq.empty())
	{
		p = pq.top();	pq.pop();
		//cout << "* 노드 [ " << p.b << " ] 꺼냈다." << endl;
		
		if (visited[p.b]) {
			//cout << "** 노드 [ " << p.b << " ]는 이미 방문했다" << endl;
			continue; 
		}
		
		// 계산에 필요한 변수들 자율적으로 선언

		visited[p.b] = 1; SL[p.b] = p.l; 
		for (i = 0; i < ED[p.b].size(); i++) 
		{
			q.l = SL[p.b] + ED[p.b][i].l;
			q.a = p.b;
			q.b = ED[p.b][i].b;
			pq.push(q);

			//cout << "방금 노드 [ " << q.b << " ] 큐에 들어갔다 (끝)" << " --- l은 : " << q.l <<"  현재 Q에는 : " << pq.size() << endl;
		}

	}
}

int main()
{
	int i, from, to, length;
	// n명의 학생이 x번 마을에 모여서 파티하는데 m개의 단방향 도로가 있음
	cin >> n >> m >> x;
	int result = 0;
	tpl tmp;

	for (i = 0; i < m; i++) {
		cin >> from >> to >> length;
		tmp.a = from; tmp.b = to; tmp.l = length; ED[from].push_back(tmp);
	}
	dijk(x);

	for (i = 1; i <= n; i++) {
		SB[i] = SL[i];
	}

	for (i = 1; i <= n; i++) {
		// visited 배열 초기화
		memset(visited, 0, sizeof(visited));
		if (i == x) continue;
		dijk(i);
		// cout << SB[i] << " & " << SL[x] << '\n';
		result = max(result, SB[i] + SL[x]);
	}

	cout << result;

	return 0;
}

기본적인 X에서 정점으로 가는 최단거리는 일반적인 다익스트라 알고리즘을 사용하면 된다.

그러나, 각 정점들에서 X로 돌아오는 최단 거리를 어떻게 구해야 하나 고민했다. 돌아오는 길을 담는 배열 SB를 선언했고, 하나의 다익스트라로 문제를 해결할 수 있었다. 꽤나 오랜시간 고민한 문제.