白駿1753-最短経路(金貨5)

質問する

白駿1753-最短経路
( https://www.acmicpc.net/problem/1753 )

これは多翼点アルゴリズムの基本的な問題である.

方法

これは最短経路を探す問題です.最短パスアルゴリズムを使用します.
定点は最大20,000個、幹線は最大30,000個です.
したがって,O(VE)を用いたベルマンフォードアルゴリズムはタイムアウトを招く.
これは開始点の最短パスです.
多翼点アルゴリズムはFloyd−Warsalアルゴリズムよりも適切である.
実施方法は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;
}