문제 출처: https://www.acmicpc.net/problem/1916
풀이
일반적인 다익스트라구현은O(V^2)이고, 우선순위큐를 활용한 다익스트라구현은 O(ElogV)인데, 입력범위를 보면
v^2=1,000,000이고, 2^10은 1024이므로 대략 ElogV=1,000,000쯤이므로 어떠한 방법을 사용하던지 pass를 받을 수 있습니다.
저는 우선순위큐를 이용한방법으로 풀었습니다.
주의할 것은, "a에서 b로 가는길이 있다는것은 b에서 a로 가는길이 있다" 를 의미하는게 아니므로, 이 문제는
무방향그래프가 아닌 방향그래프입니다. 그것말고는 딱히 주의할것은 없는 것 같습니다.
코드
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int INF = 100000000;
vector < pair<int, int>>a[1001];
int d[1001];
void dijkstra(int start);
int main()
{
cin.tie(0);
cin.sync_with_stdio(false);
int n, m, v1, v2, w, start, end;
cin >> n >> m;
for (int i = 1; i <= n; i++)
d[i] = INF;
for (int i = 0; i < m; i++)
{
cin >> v1 >> v2 >> w;
a[v1].push_back(make_pair(v2, w));
}
cin >> start >> end;
dijkstra(start);
cout << d[end] << '\n';
}
void dijkstra(int start)
{
d[start] = 0;
priority_queue<pair<int, int>>pq;
pq.push({ 0, start });
while (!pq.empty())
{
int current = pq.top().second;
int distance = -pq.top().first;
pq.pop();
//최단거리가 아니면 skip
if (d[current] < distance)
continue;
for (int i = 0; i < a[current].size(); i++)
{
int next = a[current][i].first;
int next_distance = distance + a[current][i].second;
if (d[next] > next_distance)
{
d[next] = next_distance;
pq.push(make_pair(-next_distance, next));
}
}
}
}결과
'문제풀이(BOJ) > 다익스트라' 카테고리의 다른 글
| [백준 1719] 택배 (0) | 2020.01.24 |
|---|---|
| [백준 1238] 파티 (0) | 2020.01.24 |
| [백준 1753] 최단경로 (0) | 2020.01.22 |
