where
題意
圖，無相邊，有重邊。
要找最小的路徑中cost最大的邊，並且可以往回走。
思考
因為不關路徑的長度，因此一定找最小條的路，在一條可以經過所有點的路徑中。
（其實就是 MST 在做的事啦～）
Code
#include <iostream>
#include <queue>
using namespace std;
int T, N, M, Q;
long long edge[2005][2005];
bool v[2005];
priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > q;
void ini(void){
int a, b;
long long c;
scanf("%d %d", &N, &M);
while(M--){
scanf("%d %d %lld", &a, &b, &c);
if(!edge[a][b] || edge[a][b] > c)
edge[a][b] = edge[b][a] = c;
}
}
void sol(void){
int i, x;
long long c, ans = 0;
q.push(make_pair(0,1) );
while(!q.empty()){
if(v[q.top().second]){
q.pop();
continue;
}
c = q.top().first;
x = q.top().second;
q.pop();
ans = (ans < c)? c: ans;
v[x] = 1;
for(i = 1; i <= N; i++){
if(!v[i] && edge[x][i])
q.push(make_pair(edge[x][i], i) );
}
}
printf("%lld\n", ans);
}
int main(void){
int i, j;
ini();
sol();
}
心得
沒有理解到核心，其實不用真的完全實作 MST 。