80. 다익스트라 알고리즘 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

struct Edge
{
	int node;
	int cost;
	
	Edge(int x, int y)
	{
		this -> node = x;
		this -> cost = y;
	}
	
	bool operator<(const Edge &a) const
	{
		return this -> cost > a.cost;
	}
};

int main()
{
	int n, m, a, b, c;
	scanf("%d %d", &n ,&m);
	
	vector<int> dis(n+1, 2147000000); // 각 노드까지의 거리를 무한대로 설정
	vector<pair<int,int>> v[n+1];
	priority_queue<Edge> pQ;
	
	for(int i = 1; i <= m; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		v[a].push_back(make_pair(b, c));
	}
	
	pQ.push(Edge(1, 0));
	dis[1] = 0;
	
	while(!pQ.empty())
	{
		Edge temp = pQ.top();
		pQ.pop();
		
		int node = temp.node; // 현재 노드번호
		int cost = temp.cost; // 현재 노드까지 오는데 드는 비용
		
		if(dis[node] < cost) continue; // 변경된 현재 노드까지의 비용 < 변경되기 전 비용
		
		for(int i = 0; i < v[node].size(); i++)
		{
			int nextNode = v[node][i].first; // 다음 노드번호
			int nextCost = v[node][i].second + cost; // 다음 노드까지의 비용
			
			if(dis[nextNode] > nextCost)
			{
				dis[nextNode] = nextCost;
				pQ.push(Edge(nextNode, nextCost));
			}
		}
	}
	
	for(int i = 2; i <= n; i++)
	{
		if(dis[i] != 2147000000) printf("%d : %d\n", i, dis[i]);
		else printf("%d : impossible\n", i);
	}
	
	return 0;
}