백준 1753 - 최단경로(골드 5)

문제

백준 1753 - 최단경로
(https://www.acmicpc.net/problem/1753)

다익스트라 알고리즘 기본 문제이다.

접근법

최단경로를 구하는 문제이다. 최단경로 알고리즘을 사용한다.
정점의 개수는 최대 20000개, 간선의 개수는 최대 300000개나 된다.

따라서 O(VE)인 벨만포드 알고리즘을 사용하면 시간 초과가 난다.
그리고 하나의 시작 정점에서의 최단경로이므로,
플로이드-워셜 알고리즘보다는 다익스트라 알고리즘이 적합하다.

구현 방법으로는 인접행렬 방식으로 구현하면 O(N^2)이므로
역시 시간초과가 난다.
따라서 인접리스트 방식으로 구현해야한다.
그리고 우선순위 큐를 사용한다.

구현

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 987654321 //무한값 정의
using namespace std;
typedef struct __node //리스트 노드 구조체
{
	int num;
	int cost;
}Node;
struct cmp //우선순위 큐 비교 기준
{
	bool operator() (Node& x,Node& y)
	{
		return x.cost>y.cost;
	}
};
int V,E;
int s;
int dist[20002]; // 최단경로 저장 배열
vector<Node> list[20002];

void dijkstra(int s)
{
	priority_queue<Node,vector<Node>,cmp > pq;//우선순위 큐
	Node p;
	p.num=s;
	p.cost=0; 
	pq.push(p); //시작정점 push
	dist[s]=0;
	while(!pq.empty())
	{
		Node pp=pq.top();
		pq.pop();
		
		if(dist[pp.num]>pp.cost) //큐에서 뽑은 노드의 값보다 그 노드의 경로 비용이 적은 경우 pass(시간 절약)
			continue;
			
		vector<Node>::iterator it;
		for(it=list[pp.num].begin();it!=list[pp.num].end();it++) 
		{
			if(dist[it->num]>dist[pp.num]+it->cost) //relaxation
			{
				dist[it->num]=dist[pp.num]+it->cost;
				Node np;
				np.num=it->num;
				np.cost=dist[it->num];
				pq.push(np);
			}
		}
	}
}
int main()
{
	scanf("%d %d",&V,&E);
	scanf("%d",&s);
	for(int i=1;i<=V;i++) //최단경로 저장 배열 초기화
	{
		dist[i]=INF;
	}
	for(int i=0;i<E;i++) //간선삽입
	{
		int v,w,cost;
		scanf("%d %d %d",&v,&w,&cost);
		Node p;
		p.num=w;
		p.cost=cost;
		list[v].push_back(p);
	
	}
	dijkstra(s);
	for(int i=1;i<=V;i++)
	{
		if(dist[i]==INF)
			printf("INF\n");
		else
			printf("%d\n",dist[i]);
	}
	
	
	return 0;
}