題目鏈接

題意

給定一個$n$個點 $m$條邊的無向圖
每條邊有邊權

求1-n的路徑中最小的邊權是多少
每條路可以重復走

思路

把邊按邊權降序排序
用并查集維護連通性
遍歷每條邊 每次合并邊的起點和終點
如果1和n聯通 并且這條邊在1和n的這個連通塊中
就對ans取min

Code

#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=1e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
int a[N];class UnionFind{
private:vector<int>p,s;public:int cnt=0;UnionFind(int n): p(n+1),s(n+1,1){iota(p.begin(),p.end(),0);cnt=n;}int find(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];}void merge(int u,int v){int uu=find(u),vv=find(v);if(uu!=vv){if(s[uu]>s[vv]){p[vv]=uu;s[uu]+=s[vv];}else{p[uu]=vv;s[vv]+=s[uu];}cnt--;}}bool is_connected(int u,int v){return find(u)==find(v);}int size(int x){return s[x];}
};class Solution {
public:int minScore(int n, vector<vector<int>>& roads) {UnionFind uf(n);vector<ar3>edges;for(auto e:roads){int u=e[0],v=e[1],d=e[2];edges.push_back({d,u,v});}sort(edges.begin(),edges.end(),greater<ar3>());int ans=INF;for(auto [d,u,v]:edges){uf.merge(u,v);if(uf.is_connected(1,n)){if(uf.is_connected(1,u)){cmin(ans,d);}}}return ans;}
};