[G5] 백준 6248번 Bronze Cow Party C++ 다익스트라

리뷰

 

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

점심시간에 부랴부랴 푼 기본적인 다익스트라 문제

 

 

전역 변수

• N : 배열의 최대 개수를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• x : 중심 노드의 번호를 저장할 변수
• Edge : 간선 정보를 정의할 구조체
• edges : 인접 리스트를 저장할 Edge타입 벡터 배열
• Pos : 현재 위치와 누적 가중치를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

int dijkstra()
{
	priority_queue< Pos > pq;
	pq.push( { x, 0 } );
	vector< int > dist( n + 1, 2e9 );
	dist[ x ] = 0;

	while ( !pq.empty() )
	{
		const auto [cn, cv] = pq.top(); pq.pop();
		if ( dist[ cn ] < cv )
			continue;

		for ( const auto& [nn, w] : edges[ cn ] )
		{
			int nv = cv + w;

			if ( dist[ nn ] > nv )
			{
				dist[ nn ] = nv;
				pq.push( { nn, nv } );
			}
		}
	}

	int mx = 0;
	for ( int i = 1; i <= n; ++i )
		mx = max( mx, dist[ i ] );


	return mx * 2;
}

 

목적지로부터 모든 노드까지의 최대 왕복 거리를 구하기 위한 함수

 

 

문제풀이

1. n, m, x값을 입력받고, m개의 간선 정보를 입력 받아 edges를 초기화한다.
2. dijkstra함수를 호출하여 벡터 dist에 모든 노드까지의 거리를 구한다.
3. 변수 mx를 0으로 초기화 하고, dist를 순회하며 가장 큰 값을 mx에 저장한다.
4. mx*2를 리턴하고, 리턴값을 호출한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 간선이 중복으로 들어올 수 있다.
2. 해당 부분을 N*N배열로 최소값을 기록하여 인접리스트에 저장하면 메모리는 늘지만 속도는 줄일 수 있어보인다.

 

정답 코드

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

const int N = 1001;
int n, m, x;
struct Edge
{
	int nn, w;
};
vector < Edge > edges[ N ];
struct Pos
{
	int cn, cv;
	bool operator<( const Pos& other ) const
	{
		return cv > other.cv;
	}
};

int dijkstra()
{
	priority_queue< Pos > pq;
	pq.push( { x, 0 } );
	vector< int > dist( n + 1, 2e9 );
	dist[ x ] = 0;

	while ( !pq.empty() )
	{
		const auto [cn, cv] = pq.top(); pq.pop();
		if ( dist[ cn ] < cv )
			continue;

		for ( const auto& [nn, w] : edges[ cn ] )
		{
			int nv = cv + w;

			if ( dist[ nn ] > nv )
			{
				dist[ nn ] = nv;
				pq.push( { nn, nv } );
			}
		}
	}

	int mx = 0;
	for ( int i = 1; i <= n; ++i )
		mx = max( mx, dist[ i ] );


	return mx * 2;
}

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

	cin >> n >> m >> x;
	while ( m-- )
	{
		int f, t, w; cin >> f >> t >> w;
		edges[ f ].push_back( { t, w } );
		edges[ t ].push_back( { f, w } );
	}

	cout << dijkstra();
}