結果
問題 | No.1473 おでぶなおばけさん |
ユーザー |
![]() |
提出日時 | 2024-10-17 12:30:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 243 ms / 2,000 ms |
コード長 | 824 bytes |
コンパイル時間 | 12,151 ms |
コンパイル使用メモリ | 339,196 KB |
実行使用メモリ | 20,684 KB |
最終ジャッジ日時 | 2024-10-17 12:30:25 |
合計ジャッジ時間 | 22,577 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;int main(){// input + prepint n,m;cin >> n >> m;map<int,vector<pair<int,int>>> edge;while(m--){int s,t,d;cin >> s >> t >> d;edge[-d].emplace_back(--s,--t);}// solve #1dsu uf(n);vector<vector<int>> g(n);int w = -1;for(auto p : edge){w = -p.first;for(auto [u,v] : p.second){uf.merge(u,v);g[u].push_back(v);g[v].push_back(u);}if(uf.same(0,n-1)) break;}// solve #2vector<int> dist(n,-1);queue<pair<int,int>> q;q.emplace(0,0);dist[0] = 0;while(!q.empty()){auto[now,stp] = q.front();q.pop();for(auto nxt : g[now]){if(dist[nxt] == -1){dist[nxt] = stp+1;q.emplace(nxt,stp+1);}}}// outputcout << w << " " << dist.back() << endl;}