結果
問題 |
No.1320 Two Type Min Cost Cycle
|
ユーザー |
|
提出日時 | 2024-09-23 20:41:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 342 ms / 2,000 ms |
コード長 | 1,520 bytes |
コンパイル時間 | 1,992 ms |
コンパイル使用メモリ | 200,972 KB |
最終ジャッジ日時 | 2025-02-24 11:44:38 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
コンパイルメッセージ
main.cpp: In function ‘void undir()’: main.cpp:32:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 32 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:34:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 34 | scanf("%d%d%d", &x, &y, &z); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ main.cpp: In function ‘void dir()’: main.cpp:50:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 50 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:52:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 52 | scanf("%d%d%d", &x, &y, &z); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:69:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 69 | scanf("%d", &cas); | ~~~~~^~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> typedef long long LL; const int N = 2e3 + 7; const LL INF = 0x3f3f3f3f3f3f3f3f; int n, m, pre[N]; LL dis[N]; std::vector<std::pair<int, int>> g[N]; void dijkstra(int r) { std::priority_queue<std::pair<LL, int>, std::vector<std::pair<LL, int>>, std::greater<>> q; memset(pre, 0, sizeof pre); memset(dis, 0x3f, sizeof dis); dis[r] = 0, q.push({0, r}); while(!q.empty()) { auto [d, u] = q.top(); q.pop(); if(d != dis[u]) continue; for(auto &&[v, w]: g[u]) if(dis[v] > d + w) { dis[v] = d + w; pre[v] = u; q.push({dis[v], v}); } } } void undir() { scanf("%d%d", &n, &m); for(int i = 1, x, y, z; i <= m; ++i) { scanf("%d%d%d", &x, &y, &z); g[x].emplace_back(y, z); g[y].emplace_back(x, z); } LL ans = INF; for(int r = 1; r <= n; ++r) { dijkstra(r); for(int u = 1; u <= n; ++u) for(auto &&[v, w]: g[u]) if(pre[u] != v && pre[v] != u) ans = std::min(ans, dis[u] + dis[v] + w); } printf("%lld\n", ans == INF ? -1 : ans); } void dir() { scanf("%d%d", &n, &m); for(int i = 1, x, y, z; i <= m; ++i) { scanf("%d%d%d", &x, &y, &z); g[x].emplace_back(y, z); } LL ans = INF; for(int r = 1; r <= n; ++r) { dijkstra(r); for(int u = 1; u <= n; ++u) for(auto &&[v, w]: g[u]) if(v == r) ans = std::min(ans, dis[u] + w); } printf("%lld\n", ans == INF ? -1 : ans); } int main() { int cas; scanf("%d", &cas); if(cas == 0) undir(); else dir(); return 0; }