結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー |
|
提出日時 | 2024-09-23 20:41:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 353 ms / 2,000 ms |
コード長 | 1,520 bytes |
コンパイル時間 | 10,086 ms |
コンパイル使用メモリ | 176,024 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-23 20:55:54 |
合計ジャッジ時間 | 20,114 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
コンパイルメッセージ
main.cpp: In function 'void dijkstra(int)': main.cpp:18:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 18 | auto [d, u] = q.top(); | ^ main.cpp:22:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 22 | for(auto &&[v, w]: g[u]) | ^ main.cpp: In function 'void undir()': main.cpp:42:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 42 | for(auto &&[v, w]: g[u]) | ^ main.cpp: In function 'void dir()': main.cpp:59:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 59 | for(auto &&[v, w]: g[u]) | ^
ソースコード
#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();elsedir();return 0;}