c++ 백준_1753_"최단경로"

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

1753번: 최단경로

 

우선순위큐를 사용한 다익스트라 문제이다.

​

예전에 못풀어서 놔둔 거

​

이제 우선순위 큐 다익스트라가 익숙해져서

다시 해보았다.

​

​

​

​

근돼!

​

BAAAM

​

​

​

요것의 문제는

​

endl ; 이 아닌

​

"\n";

​

를 사용해야 했다.

​

holymoly

​

출력이 최대 20,000개 정도 되니 요런 것을 신경을 써줘야됐다

​

쟁신 차려 쟁신

 

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

#define INF 1000000000

int dist[20001];
vector<pair<int, int>> node[20001];

struct comp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.second > b.second;
	}
};

void shortest_path(int N, int start) {

	priority_queue < pair<int, int>, vector<pair<int, int>>, comp> pq;

	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}

	dist[start] = 0;

	pq.push(make_pair(start, 0));

	while (!pq.empty()) {
		int weight = pq.top().second;
		int u = pq.top().first;
		pq.pop();

		if (dist[u] < weight)
			continue;

		for (int i = 0; i < node[u].size(); i++) {

			int next = node[u][i].first;
			int D = node[u][i].second;

			if (weight + D < dist[next]) {
				dist[next] = weight + D;
				pq.push(make_pair(next, dist[next]));
			}
		}
	}
}

int main(void) {
	int V, E, K;

	cin >> V >> E;
	cin >> K;


	
	int u, v, weight;
	for (int i = 0; i < E; i++) {
		cin >> u >> v >> weight;

		node[u].push_back(make_pair(v, weight));
	}


	shortest_path(V, K);

	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF)
			cout << "INF\n";
		else
			cout << dist[i] << "\n";
	}


}