백준 알고리즘 1939번 : 중량제한
링크
https://www.acmicpc.net/problem/1939
문제
N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.
영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.
한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.
출력
첫째 줄에 답을 출력한다.
예제 입력 및 출력
실패 코드(C++)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 100001
#define INF 1e18
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
vector <pair<ll,ll>> adj[MAX]; // 노드들의 정보들을 담는 벡터
vector<ll> dist(MAX,INF); //최단거리를 저장하는 배열, dist배열 초기화 해준다.
void dijkstra(ll node){
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> PQ;
PQ.push({0,node});
dist[node] = 0;
while(!PQ.empty()){
ll weight = PQ.top().first;
int cur = PQ.top().second;
PQ.pop();
if(dist[cur] < weight)
continue;
for(int i = 0; i < adj[cur].size(); i++){
int next = adj[cur][i].second;
int nWeight = adj[cur][i].first;
if(dist[next] > nWeight + weight){
dist[next] = nWeight + weight;
PQ.push(make_pair(dist[next], next));
}
}
}
}
int main(){
fastio;
int n,m;
cin >> n >> m;
for(int i = 0; i < m; i++){
ll a,b,c; cin >> a >> b >> c;
adj[a].push_back({c,b}); //adj[노드].<가중치,노드>구조
adj[b].push_back({c,a}); // 양방향 그래프
}
int start,end;
cin >> start >> end;
dijkstra(start);
cout << dist[end];
return 0;
}
Author And Source
이 문제에 관하여(백준 알고리즘 1939번 : 중량제한), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inwooleeme/백준-알고리즘-1939번-중량제한저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)