[백준] 1939번 중량제한 (C++)

https://www.acmicpc.net/problem/1939

 

 

이 문제는 N개의 노드가 입력되고 M개의 노드를 잇는 간선이 주어질때 각 간선마다 최대 중량 제한이 존재한다.

이때 시작점에서 끝점까지 이동할때 한번의 이동에서 옮길 수 있는 물품의 중량의 최댓값을 구하는 문제이다.

 

간선의 가중치가 있으며 시작점에서 끝점까지 최단거리에서 최대 용량을 구하기 위해서 다익스트라 알고리즘을 사용해야겠다고 생각을 했다.

 

또한 최대를 구하는 문제이므로 최대힙을 사용하여 문제를 해결하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, M, start, en;
const ll INF = 1e11;
vector<vector<pii>> v(10001);

void dijkstra(int a, vector<ll> &dist) {
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>> pq;
    pq.push({INF, a});
    dist[a] = INF;

    while(!pq.empty()) {
        int Node = pq.top().second;
        ll cost = pq.top().first;
        pq.pop();

        if(dist[Node] > cost) continue;

        for(auto it : v[Node]) {
            int nextNode = it.first;
            int nextCost = (cost > it.second)? it.second : cost;

            if(dist[nextNode] < nextCost) {
                pq.push({nextCost, nextNode});
                dist[nextNode] = nextCost;
            }
        }
    }
}

void solve() {
    vector<ll> dist(N+1);
    dijkstra(start, dist);

    cout << dist[en];
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >>c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }

    cin >> start >> en;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}