結果
問題 |
No.1473 おでぶなおばけさん
|
ユーザー |
![]() |
提出日時 | 2024-10-18 15:38:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,104 bytes |
コンパイル時間 | 2,446 ms |
コンパイル使用メモリ | 210,120 KB |
最終ジャッジ日時 | 2025-02-24 20:09:06 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 WA * 9 |
ソースコード
#include <bits/stdc++.h> using namespace std; void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } int main() { fast_io(); int n, m; cin >> n >> m; vector<vector<pair<int, int>>> g(n); for (int i = 0; i < m; i++) { int s, t, d; cin >> s >> t >> d; s--, t--; g[s].push_back({t, d}); g[t].push_back({s, d}); } const int INF = 1e9; vector<pair<int, int>> dist(n, {0, 1e9}); vector<bool> vis(n, false); dist[0] = {1e9, 0}; using tiii = tuple<int, int, int>; priority_queue<tiii, vector<tiii>, greater<tiii>> pq; pq.push({-1e9, 0, 0}); while (!pq.empty()) { auto [ma, d, u] = pq.top(); pq.pop(); if (vis[u]) { continue; } vis[u] = true; ma = -ma; for (auto [v, w] : g[u]) { int ma_new = min(ma, w); if (dist[v].first < ma_new) { dist[v] = {ma_new, dist[u].second + 1}; pq.push({-ma_new, dist[v].second, v}); } else if (dist[v].first == ma_new) { dist[v].second = min(dist[v].second, dist[u].second + 1); pq.push({-ma_new, dist[v].second, v}); } } } cout << dist[n - 1].first << " " << dist[n - 1].second << endl; }