| 알고리즘 |
| 다익스트라 |
[문제 본문]
문제
농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.
농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.
다음 지도를 참고하세요.
[2]---
/ | \
/1 | \ 6
/ | \
[1] 0| --[3]
\ | / \2
4\ | /4 [6]
\ | / /1
[4]-----[5]
3
농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.
농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.
입력
첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.
둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.
출력
첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.
예제 입력 1
6 8 4 5 3 2 4 0 4 1 4 2 1 1 5 6 1 3 6 2 3 2 6 3 4 4
예제 출력 1
5
[푼 코드]
#include <iostream>
#include <vector>
#include <queue>
#define MAXNUM 50001
#define INF 987654321
using namespace std;
int N, M;
vector<pair<int,int>> v[MAXNUM];
int d[MAXNUM];
int Solved(int start, int end)
{
priority_queue<pair<int, int>> pq;
d[start] = 0;
pq.push({ 0,start });
while (!pq.empty())
{
int cost = -pq.top().first;
int cur = pq.top().second;
pq.pop();
for (auto iter = v[cur].begin(); iter < v[cur].end(); iter++)
{
int i_goal = iter->first;
int i_cost = iter->second;
if (d[i_goal] > d[cur] + i_cost)
{
d[i_goal] = d[cur] + i_cost;
pq.push({ -i_cost,i_goal });
}
}
}
return d[end];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int s, e, c;
cin >> N >> M;
for (int i = 1; i <= N; i++)
{
d[i] = INF;
}
for (int i = 0; i < M; i++)
{
cin >> s >> e >> c;
v[s].push_back({ e, c });
v[e].push_back({ s, c });
}
cout << Solved(1,N);
return 0;
}
#다익스트라 #백준5972 #백준다익스트라 #최단경로알고리즘
'알고리즘 > 백준 알고리즘 공부' 카테고리의 다른 글
| [플로이드–와샬] (백준 2458) 키 순서 (0) | 2022.03.15 |
|---|---|
| [플로이드–와샬] (백준 2660) 회장뽑기 (0) | 2022.03.15 |
| [다익스트라] (백준 9370) 미확인 도착지 (0) | 2022.03.15 |
| [다익스트라] (백준 4485) 녹색 옷 입은 애가 젤다지? (0) | 2022.03.14 |
| [그리디] (백준 1080) 행렬 (0) | 2022.03.13 |