結果
問題 |
No.1473 おでぶなおばけさん
|
ユーザー |
![]() |
提出日時 | 2021-04-09 22:36:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 2,000 ms |
コード長 | 878 bytes |
コンパイル時間 | 1,593 ms |
コンパイル使用メモリ | 171,916 KB |
実行使用メモリ | 14,976 KB |
最終ジャッジ日時 | 2024-06-25 06:13:52 |
合計ジャッジ時間 | 7,220 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
#include<bits/stdc++.h> using namespace::std; const int N = 100000 + 5; int n; int m; int D[N]; vector<int> G[N]; vector<int> W[N]; void BFS(int src, int limit){ queue<int> Q; for(int i = 1; i <= n; i++) D[i] = -1; Q.emplace(src); D[src] = 0; while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = 0; i < G[u].size(); i++){ int v = G[u][i]; int w = W[u][i]; if(limit <= w and D[v] == -1){ D[v] = D[u] + 1; Q.emplace(v); } } } } int main(){ scanf("%d %d", &n, &m); for(int i = 1; i <= m; i++){ int u, v, w; scanf("%d %d %d", &u, &v, &w); G[u].emplace_back(v); G[v].emplace_back(u); W[u].emplace_back(w); W[v].emplace_back(w); } int lo = 1, hi = 1e9; while(lo < hi){ int mi = lo + (hi - lo + 1) / 2; BFS(1, mi); if(D[n] != -1) lo = mi; else hi = mi - 1; } BFS(1, lo); printf("%d %d\n", lo, D[n]); return 0; }