白駿アルゴリズム14284号:幹線接続2
12952 ワード
リンク
https://www.acmicpc.net/problem/14284
質問する
n個の頂点,0本の幹線からなる無方向図を与えた.次に、m本の重み付け幹線情報を有する幹線リストを与える.グラフに幹線リストの幹線が追加されます.このとき、特定の頂点sとtが接続された時点で、幹線の追加が停止する.接続とは、2つの頂点が幹線でアクセスできることを意味します.
sとtの接続点の幹線の重み付けと最小値に加えられた幹線の順序を調整する場合、その最大値を求める.
入力
1行目は頂点の個数n,幹線リストの幹線数mを与える.(2≤n≤5000,1≤m≤100,000)
次のm行にはa,b,cがあり、これはaとbにcの重み付けがあることを示す.(1≤a,b≤n,1≤c≤100,a≠b)
次の行は2つの頂点s,tを与える.(1≤s,t≤n,s≠t)
すべての幹線を接続すると、図形は接続図形になることを保証します.
しゅつりょく
sとt接続点の幹線重み付けの最大値を出力します.
入力と出力の例
解法
これは方向図がないことを覚えておいてください.
問題がうまく読めなかったので,1度答えをまちがえた
プールコード(C++)
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define MAX 5001
#define INF 1e9
#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>;
#define sz(a) int((a).size())
vector<pii> adj[MAX];
vector<int> dist(MAX, INF);
void dijk(int start,int end){
priority_queue<pii, vector<pii>,greater<pii>> pq;
dist[start] = 0;
pq.push({0, start});
while(!pq.empty()){
int weight = pq.top().first;
int cur = pq.top().second;
pq.pop();
if(cur == end) return;
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({dist[next], next});
}
}
}
}
int main(){
fastio;
int n,m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u,v,w; cin >> u >> v >> w;
adj[u].pb({w,v});
adj[v].pb({w,u});
}
int s,t; cin >> s >> t;
dijk(s, t);
cout << dist[t] << "\n";
return 0;
}
Reference
この問題について(白駿アルゴリズム14284号:幹線接続2), 我々は、より多くの情報をここで見つけました https://velog.io/@inwooleeme/백준-알고리즘-14284번-간선-이어가기-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol