[C/C++] 백준 #1939 중량제한(그래프)

이번 문제는 프림이나 다익스트라와 비슷하게 동작하지만, 경로에 걸쳐있는 간선중, 최소값의 간선값이 해당 경로값이 됩니다.  이 경로값이 가장 큰 것을 찾는 문제입니다.

 

weight limit

 

그래서 프림 알고리즘이나 다익스트라 알고리즘을 곧이 곧대로 사용할 수가 없습니다.

 

제가 사용한 탐욕 방법은 이것입니다.

 

0) 모든 노드의 값을 0으로 초기화합니다.

1) 출발지점에서 가장 큰 노드값을 가지고 있는 노드를 선택합니다.

2) 이동할 수 있는 모든 간선들을 적용하여 도착할 곳의 노드값을 결정합니다.  도착할 노드값은 현재보다 큰 경우 노드값을 저장하고, 우선순위큐에 해당 값을 넣습니다.

3) 도착지점이 가장 큰 노드값인 경우 종료합니다.  이 상태에서 선택할 수 있는 다른 노드값은 도착지점보다 적은 값이므로 의미가 없습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1939 - Weight Limit
//        - by Aubrey Choi
//        - created at 2019-07-14
//------------------------------------------------
#include <stdio.h>
#include <vector>
#include <queue>
#define MAXP    1000000000LL

struct Link
{
    Link(int a,int b):to(a),p(b){}
    int to, p;
};
int main()
{
    int n, m, start, end;
    static int nodes[10000];
    std::vector<Link> links[10000];
    std::priority_queue<long long> queue;
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int s, t, p;
        scanf("%d%d%d", &s, &t, &p);
        links[s-1].push_back(Link(t-1,p));
        links[t-1].push_back(Link(s-1,p));
    }
    scanf("%d%d", &start, &end); start--; end--;
    queue.push(MAXP<<32 | start);
    for(;;)
    {
        int p = queue.top() >> 32;
        int s = queue.top() & 0xffffffff;
        queue.pop();
        if(s == end) break;
        for(auto &t:links[s])
        {
            int np = t.p < p ? t.p : p, to = t.to;
            if(np > nodes[to])
            {
                nodes[to] = np;
                queue.push(((long long)np) << 32 | to);
            }
        }
    }
    printf("%d\n", nodes[end]);
}