[99클럽/파이썬 챌린저/31일차] 택배 배송

백준 5972번 택배 배송 G5

 

문제
농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다. 농부 현서에게는 지도가 있습니다. 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에 있습니다. 다음 지도를 참고하세요. 농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야 할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

입력
첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다. 둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.

출력
첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.

 

 

그래프 이론, 최단 경로, 데이크스트라

 

양방향 그래프에서 1번 정점에서 n번 정점까지의 최단 경로를 구하는 문제이다

우선순위 큐를 사용한 데이크스트라 알고리즘으로 해결했다.

 

 

import sys
import heapq

n, m = map(int, sys.stdin.readline().split())
visit = [False] * (n+1)
routes = [[] for _ in range(n+1)]
for _ in range(m):
    v1, v2, c = map(int, sys.stdin.readline().split())
    routes[v1].append((v2, c))
    routes[v2].append((v1, c))

hq = [[0, 1]]

while hq:
    c, v = heapq.heappop(hq)
    if v == n:
        print(c)
        break
    if visit[v]: continue
    visit[v] = True
    for vv, cc in routes[v]:
        if visit[vv]: continue
        heapq.heappush(hq, (c+cc, vv))

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m; cin>>n>>m;
    vector<vector<pair<int, int>>> routes;
    routes.resize(n+1);
    bool visit[n+1] = {false, };
    
    while(m--)
    {
        int v1, v2, c; cin>>v1>>v2>>c;
        routes[v1].push_back(make_pair(c, v2));
        routes[v2].push_back(make_pair(c, v1));
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> hq;

    hq.push(make_pair(0, 1));

    while (!hq.empty())
    {
        int c, v;
        c = hq.top().first;
        v = hq.top().second;
        hq.pop();
        
        if (visit[v]) continue;
        visit[v] = true;

        if(v == n)
        {
            cout<<c;
            break;
        }

        for (auto data : routes[v])
        {
            if (visit[data.second]) continue;
            hq.push(make_pair(c + data.first, data.second));
        }
    }
    
    return 0;
}

---