結果
問題 |
No.1473 おでぶなおばけさん
|
ユーザー |
👑 ![]() |
提出日時 | 2021-04-09 21:54:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 2,000 ms |
コード長 | 1,124 bytes |
コンパイル時間 | 3,619 ms |
コンパイル使用メモリ | 208,992 KB |
最終ジャッジ日時 | 2025-01-20 14:16:07 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:23:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 23 | scanf("%d%d",&N,&M); | ~~~~~^~~~~~~~~~~~~~ main.cpp:25:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 25 | rep(i,M){ int u,v,w; scanf("%d%d%d",&u,&v,&w); u--; v--; edges[i]={u,v,w}; } | ~~~~~^~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; #define rep(i,n) for(int i=0; i<(n); i++) struct DSU{ vector<int> V; DSU(int n=0){ V.resize(n); rep(i,n) V[i]=i; } int leader(int a){ return (V[a]==a)?a:(V[a]=leader(V[a])); } void merge(int u,int v){ V[leader(u)]=leader(v); } }; struct Edge{ int u,v,w; }; bool compEdge_w(Edge l, Edge r){ return l.w>r.w; } int N,M; vector<Edge> edges; vector<vector<int>> E; DSU dsu; vector<int> D; int main(){ scanf("%d%d",&N,&M); edges.resize(M); rep(i,M){ int u,v,w; scanf("%d%d%d",&u,&v,&w); u--; v--; edges[i]={u,v,w}; } sort(edges.begin(),edges.end(),compEdge_w); E.resize(N); dsu = DSU(N); int W=1001001001; for(Edge& e:edges){ dsu.merge(e.u,e.v); W = e.w; if(dsu.leader(0) == dsu.leader(N-1)) break; } for(Edge& e:edges) if(e.w>=W){ E[e.u].push_back(e.v); E[e.v].push_back(e.u); } D.assign(N,-1); queue<int> Q; D[0]=0; Q.push(0); while(Q.size()){ int p=Q.front(); Q.pop(); for(int e:E[p]) if(D[e]==-1){ D[e] = D[p]+1; Q.push(e); } } printf("%d %d\n",W,D[N-1]); return 0; }