알고리즘 문제
[백준] 1753번 최단경로
feelcoding
2020. 2. 4. 01:52
728x90
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두
www.acmicpc.net
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<pair<int, int>> adj[20002];
int length[20002];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; //비용 적은 것이 우선이 되게 오름차순 정렬
bool visited[20002];
int main() {
int numOfVertex, numOfEdge, startNode;
cin >> numOfVertex >> numOfEdge >> startNode;
const int INF = 2147483647;
int from, to, weight;
for (int i = 0; i < numOfEdge; i++) {
cin >> from >> to >> weight;
adj[from].push_back(pair<int, int>(weight, to)); //pair의 앞쪽에 있는 숫자를 기준으로 오름차순 정렬하므로 가중치를 앞에 둔다.
}
for (int i = 1; i <= numOfVertex; i++) {
length[i] = INF;
}
length[startNode] = 0; //나에서 나로 가는 최단경로는 0
q.push(make_pair(0, startNode));
while (!q.empty()) {
int cost = q.top().first;
int now = q.top().second;
q.pop();
if (length[now] < cost || visited[now]) continue;
visited[now] = true;
for (int i = 0; i < adj[now].size(); i++) {
if (length[adj[now][i].second] > adj[now][i].first + cost) {
q.push(make_pair(adj[now][i].first + cost, adj[now][i].second));
length[adj[now][i].second] = adj[now][i].first + cost;
}
}
}
for (int i = 1; i <= numOfVertex; i++) {
if (length[i] >= INF) cout <<"INF\n";
else cout << length[i] << '\n';
}
return 0;
}728x90