백준 11085

문제

전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 이에 비례하는 수의 군사가 지나갈 수 있습니다.

Baekjoon World의 국왕은 군사들이 뭉치는 것이 유리하다고 생각해서, 미리 Cube World로 가는 경로를 정해 두고 그 경로로만 모든 군사를 보냈습니다. Baekjoon World의 국왕은 총명해서, 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택했습니다.

그런데 전쟁 때문에 어느 길로 보냈는지에 대한 기록이 불타 없어져 버렸습니다. 전쟁사를 완성하려면 이 기록이 꼭 필요합니다. 위대한 과학자인 당신이 다시 복구해 주세요.

입력

첫 줄에 p와 w가 공백을 사이에 두고 주어집니다. (2 ≤ p ≤ 1 000; 1 ≤ w ≤ 50 000)

다음 줄에 Baekjoon World의 수도 c와 Cube World의 수도 v가 공백을 사이에 두고 주어집니다. (0 ≤ c, v < p; c ≠ v)

다음 w줄에 길이 연결하는 두 지점 wstart, wend,와 길의 너비 wwidth가 공백을 사이에 두고 주어집니다. (0 ≤ wstart, wend < p; wstart ≠ wend; 1 ≤ wwidth ≤ 1 000)

출력

첫 줄에 Baekjoon World의 국왕이 정한 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 출력합니다.

풀이

Backjoon World의 수도에서 Cube World의 수도까지 가는길의 넓이의 최소값들 중에 가장 큰 값을 구하면 되는 문제이다.

출발지가 정해져 있지만 여러가지 경로를 모두 고려해야되는 문제이니 다익스트라를 이용한 풀이는 제한된다.

여러가지 풀이가 있겠지만, 우선 나는 기본적으로 모든 경로와 간선을 이용하고, 조건을 통해 몇가지 케이스를 제거해주는 방법을 택했다.

backjoon world의 수도를 기준으로, 간선의 개수가 적은 노드부터 방문하게 하기 위해 BFS를 선택했고, 노드를 방문할때마다 길의 너비를 갱신하여 만약 해당 노드의 넓이가 이전노드에서 오는 간선의 넓이, 이전노드 까지의 간선의 넓이의 min값 보다 클 경우에는 그 노드를 다시 방문하지 않도록 했다.

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int p, w, c, v, ans;
int vis[1001], dist[1001];
vector<vector<pair<int,int>>>graph(1001);
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>p>>w>>c>>v;
    for(int i=0; i<w; i++){
        int st, dest, wid;
        cin>>st>>dest>>wid;
        graph[st].push_back({dest, wid});
        graph[dest].push_back({st, wid});
    }
    queue<int>q;
    q.push(c);
    dist[c] = 987654321;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(auto e : graph[cur]){
            if(dist[e.first] >= min(dist[cur], e.second)) continue;
            dist[e.first] = min(dist[cur], e.second);
            q.push(e.first);
        }
    }
    cout<<dist[v];


}