結果
問題 |
No.1320 Two Type Min Cost Cycle
|
ユーザー |
![]() |
提出日時 | 2025-02-09 18:15:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 331 ms / 2,000 ms |
コード長 | 1,116 bytes |
コンパイル時間 | 2,156 ms |
コンパイル使用メモリ | 205,800 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-09 18:16:03 |
合計ジャッジ時間 | 6,859 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#include <bits/stdc++.h> using namespace std; void fast_io() { ios::sync_with_stdio(false); std::cin.tie(nullptr); } int main() { fast_io(); int t; cin >> t; int n, m; cin >> n >> m; vector<vector<pair<int, long long>>> g(n); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u--, v--; g[u].push_back({v, w}); if (t == 0) { g[v].push_back({u, w}); } } long long ans = 1e18; for (int u0 = 0; u0 < n; u0++) { for (auto [v0, w0] : g[u0]) { vector<long long> dist(n, 1e18); dist[v0] = 0; using pli = pair<long long, int>; priority_queue<pli, vector<pli>, greater<pli>> pq; pq.push({0, v0}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) { continue; } for (auto [v, w] : g[u]) { if (u == u0 && v == v0) { continue; } if (t == 0 && u == v0 && v == u0) { continue; } if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } ans = min(ans, dist[u0] + w0); } } if (ans >= 1e17) { ans = -1; } cout << ans << endl; }