BaekJoon 1238번: 파티(C++)

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

1238번: 파티

풀이법

1) 다익스트라 알고리즘을 사용하면 풀 수 있는 문제이다.

2) From배열과 To배열로 나누어서, 방문할 마을까지의 최소거리 + 다시 돌아가는 최소거리를 최종 배열일 dist에 넣고 가장 긴 것을 찾으면 되는 문제이다.

3) 다익스트라 알고리즘을 알고 있다면 쉽게 풀 수 있으나, 모르는 경우 어려울 수 있는 문제이기에 기초 개념을 꼭 익히는 것을 추천한다.

#include <algorithm>
#include <iostream>
#include <queue>
#include<vector>
using namespace std;

int n, m, x;
int arr[1001][1001];
vector<int> dist;
int todist[1001];
int fromdist[1001];

void dijkFrom(int start)
{
	for (int i = 1; i <= n; i++)
	{
		fromdist[i] = 100000000;
	}
	fromdist[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,start });
	while (!pq.empty())
	{
		int cost = pq.top().first;
		int curIndex = pq.top().second;
		pq.pop();
		if (cost > fromdist[curIndex])
			continue;
		for (int i = 1; i <= n; i++)
		{
			if (arr[curIndex][i] == 0)
				continue;
			int nextCost = cost + arr[curIndex][i];
			if (nextCost < fromdist[i])
			{
				fromdist[i] = nextCost;
				pq.push({ nextCost,i });
			}
			
		}
	}
}
void dijkTo(int start)
{
	for (int i = 1; i <= n; i++)
	{
		todist[i] = 100000000;
	}
	todist[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,start });
	while (!pq.empty())
	{
		int cost = pq.top().first;
		int curIndex = pq.top().second;
		pq.pop();
		if (cost > todist[curIndex])
			continue;
		for (int i = 1; i <= n; i++)
		{
			if (arr[curIndex][i] == 0)
				continue;
			int nextCost = cost + arr[curIndex][i];
			if (nextCost < todist[i])
			{
				todist[i] = nextCost;
				pq.push({ nextCost,i });
			}
		}
	}
}


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m >> x;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		arr[a][b] = c;
	}
	dijkFrom(x); //x에서 각 값의로의 거리

	for (int i = 1; i <= n; i++)
	{
		dijkTo(i);
		dist.push_back(fromdist[i]+todist[x]);
	}
	sort(dist.begin(), dist.end());
	cout<<dist[dist.size() - 1];
}