백준 1939 중량제한 C++

 

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

1939번: 중량제한

오랜만에 문제를 풀어보았습니다. (사실 그 전에 푼 거 틀린 거 다시 풀기....)

 

주어진 그래프에서 경로의 최소 값 중 최대값을 구하면 됩니다. 여러 방법이 있지만 가장 쉽게 떠오르는 다익스트라를 이용해서 풀었습니다.

다익스트라가 경로를 탐색하면서 기존 결과보다 좋으면 업데이트를 반복하는 것이므로, 일반적인 다익스트라처럼 합을 계산하는 것이 아닌, 최소값을 업데이트합니다.

업데이트 조건은 기존보다 클 때 (최소값 중 최대값을 구하는 것이므로) 업데이트합니다. 

(이미 업데이트된 노드 체크하는 부분을 빼먹어서 계속 시간초과가 떴다....)

 

코드는 다음과 같습니다.

 

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

using namespace std;

int n, m;
int a, b, c;
int src, dest;

// vec[i] : {연결된 노드, 둘 사이 무게}
vector<pair<int, int>> vec[10001];
// scr와 i번 노드까지 계산된 최소 무게
int weight[10001];

void init()
{
  cin >> n >> m;
  for(int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    if(a == b)
      continue;
    vec[a].push_back({b, c});
    vec[b].push_back({a, c});
  }

  cin >> src >> dest;

  // c >= 1
  memset(weight, 0, sizeof(weight));
}

void dijk()
{
  priority_queue<pair<int, int>> pq;

  pq.push({0, src});
  weight[src] = 0;

  while(!pq.empty()) {
    int w = pq.top().first;
    int node = pq.top().second;
    pq.pop();

    if(weight[node] > w)
      continue;

    for(auto v : vec[node]) {
      int nextNode = v.first;
      int nextWeight = v.second;
      int tmpWeight = 0;
      if(w == 0)
        tmpWeight = nextWeight;
      else
        tmpWeight = min(w, nextWeight);
      
      if(weight[nextNode] < tmpWeight) {
        weight[nextNode] = tmpWeight;
        pq.push({tmpWeight, nextNode});
      }
    }
  }

  cout << weight[dest];
}

int main()
{
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  init();
  dijk();
}