結果
問題 |
No.1473 おでぶなおばけさん
|
ユーザー |
![]() |
提出日時 | 2021-04-09 21:55:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 2,210 bytes |
コンパイル時間 | 1,348 ms |
コンパイル使用メモリ | 122,704 KB |
最終ジャッジ日時 | 2025-01-20 14:17:52 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <map> #include <queue> #include <iomanip> #include <set> #include <tuple> #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template<class T> void chmin(T &a,const T &b){if(a>b) a=b;} template<class T> void chmax(T &a,const T &b){if(a<b) a=b;} class DisjointSet{ public: int N; vector<int> rank,p; vector<int> sz; DisjointSet(){} DisjointSet(int n):N(n),rank(n),p(n),sz(n){ for(int i=0;i<N;i++) makeSet(i); } void makeSet(int x){ p[x]=x; rank[x]=0; sz[x]=1; } bool same(int x,int y){ return leader(x)==leader(y); } void unite(int x,int y){ if(same(x,y)) return; link(leader(x),leader(y)); } void link(int x,int y){ if(rank[x]>rank[y]) swap(x,y); p[x]=y; sz[y]+=sz[x]; if(rank[x]==rank[y]){ ++rank[y]; } } int leader(int x){ if(x!=p[x]) p[x]=leader(p[x]); return p[x]; } int size(int x){ return sz[leader(x)]; } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,M; cin>>N>>M; vector<tuple<int,int,int>> edges; rep(i,M){ int a,b,c; cin>>a>>b>>c; a--;b--; edges.push_back(mkt(a,b,c)); } vector<int> ord(M,0); rep(i,M) ord[i]=i; sort(all(ord),[&](int a,int b){ if(get<2>(edges[a])!=get<2>(edges[b])) return get<2>(edges[a]) > get<2>(edges[b]); return a<b; }); DisjointSet us(N); int lastCost=-1; for(auto i:ord){ auto [a,b,c]=edges[i]; us.unite(a,b); if(us.same(0,N-1)){ lastCost=c; break; } } vector<vector<int>> g(N); for(auto i:ord){ auto [a,b,c]=edges[i]; if(c>=lastCost){ g[a].push_back(b); g[b].push_back(a); } } queue<int> Q; vector<int> dist(N,MOD); dist[0]=0; Q.push(0); while(!Q.empty()){ int now=Q.front(); Q.pop(); for(auto nex:g[now]){ if(dist[nex]==MOD){ dist[nex]=dist[now]+1; Q.push(nex); } } } cout<<lastCost<<" "<<dist[N-1]<<endl; return 0; }