結果
問題 | No.1473 おでぶなおばけさん |
ユーザー |
|
提出日時 | 2021-04-09 21:33:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 2,207 bytes |
コンパイル時間 | 1,786 ms |
コンパイル使用メモリ | 98,600 KB |
最終ジャッジ日時 | 2025-01-20 13:43:33 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
#line 2 "/Users/tiramister/CompetitiveProgramming/Cpp/CppLibrary/Graph/bfs.hpp" #line 2 "/Users/tiramister/CompetitiveProgramming/Cpp/CppLibrary/Graph/graph.hpp" #include <vector> template <class Cost = int> struct Edge { int src, dst; Cost cost; Edge() = default; Edge(int src, int dst, Cost cost = 1) : src(src), dst(dst), cost(cost){}; bool operator<(const Edge<Cost>& e) const { return cost < e.cost; } bool operator>(const Edge<Cost>& e) const { return cost > e.cost; } }; template <class Cost = int> struct Graph : public std::vector<std::vector<Edge<Cost>>> { using std::vector<std::vector<Edge<Cost>>>::vector; void span(bool direct, int src, int dst, Cost cost = 1) { (*this)[src].emplace_back(src, dst, cost); if (!direct) (*this)[dst].emplace_back(dst, src, cost); } }; #line 4 "/Users/tiramister/CompetitiveProgramming/Cpp/CppLibrary/Graph/bfs.hpp" #include <queue> template <class Cost> std::vector<Cost> bfs(const Graph<Cost>& graph, int s) { std::vector<Cost> dist(graph.size(), -1); dist[s] = 0; std::queue<int> que; que.push(s); while (!que.empty()) { auto v = que.front(); que.pop(); for (const auto& e : graph[v]) { if (dist[e.dst] != -1) continue; dist[e.dst] = dist[v] + e.cost; que.push(e.dst); } } return dist; } #line 2 "main.cpp" #include <atcoder/dsu> #include <iostream> #include <algorithm> #line 6 "main.cpp" #include <tuple> using namespace std; void solve() { int n, m; cin >> n >> m; vector<tuple<int, int, int>> es(m); for (auto& [d, u, v] : es) { cin >> u >> v >> d; --u, --v; } sort(es.rbegin(), es.rend()); atcoder::dsu dsu(n); int nd = 0; for (auto [d, u, v] : es) { dsu.merge(u, v); if (dsu.same(0, n - 1)) { nd = d; break; } } Graph<> graph(n); for (auto [d, u, v] : es) { if (d >= nd) graph.span(false, u, v); } cout << nd << " " << bfs(graph, 0)[n - 1] << "\n"; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }