#1. 문제
https://www.acmicpc.net/problem/1446
#2. 풀이
1. 다익스트라
다익스트라 알고리즘은 '단일-출발' 최단 경로 알고리즘입니다. 시작 정점을 기준으로 다른 모든 정점에 대하여 최단 경로 값을 찾는 알고리즘으로, 일반적으로 우선순위 큐와 BFS를 활용합니다.
2. 유방향 그래프에 대한 다익스트라 알고리즘!
- 먼저, 유방향 그래프를 구성합니다. 지름길 외에도 각 지점마다 '지름길'이 아닌 일반 길에 대한 경로도 추가해주어야 합니다.
- 다음으로, 0을 출발 정점으로 설정한 다익스트라를 수행합니다. '유방향' 그래프에 대한 다익스트라의 경우 '방문 여부' 대신 현재 최단 경로 값이 현재 정점의 최단 경로 값보다 작을 경우에만 수행할 수 있도록 작성합니다.
#3. 코드
/*
<<<<<<< HEAD
@문제 : 유방향 그래프,
=======
@문제 : 주어진 지름길 목록을 통해 도착점 까지의 최단 경로 찾기
@설명
1. 다익스트라 활용
2. 그래프 구성 시 지름길 외 일반 경로에 대한 내용도 추가
>>>>>>> 186a492418d48ecfac2bba86f20016dde3a4a5b2
*/
#include <iostream>
#include <vector>
using namespace std;
#include <queue>
#include <climits>
using namespace std;
#define MAX 10001
int N, D;
vector<pair<int, int>> graph[MAX];
void dijkstra()
{
// 최단 경로 목록
vector<int> dist(MAX, INT_MAX);
// 우선순위 큐, pair< dist, node >
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty())
{
int cur = pq.top().second;
int curDist = pq.top().first;
pq.pop();
if (curDist > dist[cur])
continue;
for (const auto edge : graph[cur])
{
int neighbor = edge.first;
int weight = edge.second;
if (neighbor > D)
continue;
if (dist[neighbor] > curDist + weight)
{
dist[neighbor] = curDist + weight;
pq.push({dist[neighbor], neighbor});
}
}
}
cout << dist[D];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> D;
for (int i = 0; i <= D; ++i)
graph[i].push_back({i + 1, 1});
while (N--)
{
int u, v, w;
cin >> u >> v >> w;
// 지름길 : v-u 거리가 w보다 클 때만 지름길이다!
if (v <= D && v - u > w)
graph[u].push_back({v, w});
}
// 다익스트라
dijkstra();
return 0;
}
'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글
[BOJ알고리즘, C++]#5670_휴대폰 자판, Trie 자료구조, 트리 (0) | 2024.06.21 |
---|---|
[BOJ알고리즘, C++]#1735_분수 합, 유클리드 호제법, 최대 공약수, 최소 공배수, gcd, lcm (0) | 2024.06.19 |
[BOJ알고리즘, C++]#15657_N과M(8), 백트래킹, 조합 (0) | 2024.06.19 |
[BOJ알고리즘, C++]#1135_뉴스 전하기, DFS (0) | 2024.06.19 |
[BOJ알고리즘, C++]#14502_연구소, 백트래킹, DFS, BFS (1) | 2024.06.19 |