結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー |
![]() |
提出日時 | 2020-12-19 19:14:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 294 ms / 2,000 ms |
コード長 | 2,159 bytes |
コンパイル時間 | 943 ms |
コンパイル使用メモリ | 105,292 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-21 10:33:21 |
合計ジャッジ時間 | 4,688 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
/* -*- coding: utf-8 -*-** 1320.cc: No.1320 Two Type Min Cost Cycle - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 2000;const int MAX_M = 2000;const long long LINF = 0x7f7f7f7f7f7f7f7fLL;/* typedef */typedef long long ll;typedef pair<int,int> pii;typedef pair<ll,int> pli;typedef vector<pii> vpii;struct Edge {int u, v, w;Edge() {}Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}};/* global variables */vpii nbrs[MAX_N];Edge es[MAX_M];ll ds[MAX_N];int gs[MAX_N];/* subroutines *//* main */int main() {int t, n, m;scanf("%d%d%d", &t, &n, &m);for (int i = 0; i < m; i++) {int u, v, w;scanf("%d%d%d", &u, &v, &w);\u--, v--;nbrs[u].push_back(pii(v, w));if (t == 0) nbrs[v].push_back(pii(u, w));es[i] = Edge(u, v, w);}ll mind = LINF;for (int st = 0; st < n; st++) {memset(ds, 0x7f, sizeof(ds));ds[st] = 0;gs[st] = -1;priority_queue<pli> q;q.push(pli(0, st));while (! q.empty()) {pli u = q.top(); q.pop();ll ud = -u.first;int ui = u.second;if (ds[ui] != ud) continue;vpii &nbru = nbrs[ui];for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {int vi = vit->first;ll vd = ud + vit->second;if (ds[vi] > vd) {ds[vi] = vd;gs[vi] = (ui == st) ? vi : gs[ui];q.push(pli(-vd, vi));}}}for (int i = 0; i < m; i++) {Edge &e = es[i];if (t == 0) {if (ds[e.u] < LINF && ds[e.v] < LINF &&gs[e.u] >= 0 && gs[e.v] >= 0 && gs[e.u] != gs[e.v]) {ll d = ds[e.u] + ds[e.v] + e.w;if (mind > d) mind = d;}}else {if (ds[e.u] < LINF && e.v == st) {ll d = ds[e.u] + e.w;if (mind > d) mind = d;}}}}printf("%lld\n", (mind >= LINF) ? -1LL : mind);return 0;}