結果
問題 |
No.1320 Two Type Min Cost Cycle
|
ユーザー |
![]() |
提出日時 | 2024-02-11 02:31:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,848 ms / 2,000 ms |
コード長 | 2,685 bytes |
コンパイル時間 | 2,516 ms |
コンパイル使用メモリ | 214,476 KB |
最終ジャッジ日時 | 2025-02-19 04:51:40 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<int, int>; #define rep(i, n) for (int i = 0; i < (int)(n); i++) const ll inf = 1LL << 60; struct Edge { int to; ll w; Edge(int to, ll w) : to(to), w(w) {} }; struct Query { int a, b; ll w; Query(int a, int b, ll w) : a(a), b(b), w(w) {} }; using Graph = vector<vector<Edge>>; template <class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } else return false; } template <class T> void print(vector<T> v) { rep(i, v.size()) { cout << v[i] << " "; } cout << endl; return; } vector<ll> dijkstra(Graph &G, int s, set<P> &S) { int N = G.size(); vector<ll> dist(N, inf); vector<ll> mindist(N, inf); vector<bool> seen(N, false); priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q; Q.push({0, s * (N + 1)}); while (!Q.empty()) { ll u = Q.top().second; ll d = Q.top().first; int v, p; p = u % (N + 1); v = u / (N + 1); Q.pop(); if (seen[v]) continue; seen[v] = true; dist[v] = d; S.insert({v, p - 1}); for (auto e : G[v]) { if (seen[e.to]) continue; ll newdist = dist[v] + e.w; if (newdist >= mindist[e.to]) continue; mindist[e.to] = newdist; Q.push({mindist[e.to], e.to * (N + 1) + v + 1}); } } return dist; } int main() { int T; cin >> T; int N, M; cin >> N >> M; vector<Query> E; Graph G(N); rep(i, M) { int u, v; ll w; cin >> u >> v >> w; u--; v--; E.push_back(Query(u, v, w)); G[u].push_back(Edge(v, w)); if (T == 0) G[v].push_back(Edge(u, w)); } ll ans = inf; if (T == 0) { ll temp = inf; rep(s, N) { set<P> S; vector<ll> D = dijkstra(G, s, S); for (auto q : E) { if (S.count({q.a, q.b}) || S.count({q.b, q.a})) continue; chmin(temp, D[q.a] + D[q.b] + q.w); } chmin(ans, temp); } } else { rep(s, N) { set<P> S; ll temp = inf; vector<ll> D = dijkstra(G, s, S); for (auto q : E) { if (q.b != s) continue; chmin(temp, D[q.a] + q.w); } chmin(ans, temp); } } if (ans != inf) cout << ans << endl; else cout << -1 << endl; return 0; }