結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー |
![]() |
提出日時 | 2020-12-17 08:44:38 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 470 ms / 2,000 ms |
コード長 | 2,650 bytes |
コンパイル時間 | 5,870 ms |
コンパイル使用メモリ | 166,968 KB |
最終ジャッジ日時 | 2025-01-17 02:21:32 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#pragma GCC target ("avx2")// #pragma GCC optimization ("O3")#pragma GCC optimization ("unroll-loops")#include <iostream>#include <array>#include <algorithm>#include <vector>#include <bitset>#include <set>#include <unordered_set>#include <cmath>#include <complex>#include <deque>#include <iterator>#include <numeric>#include <map>#include <unordered_map>#include <queue>#include <stack>#include <string>#include <tuple>#include <utility>#include <limits>#include <iomanip>#include <functional>#include <cassert>// #include <atcoder/all>using namespace std;using ll=long long;template<class T> using V = vector<T>;template<class T, class U> using P = pair<T, U>;using vll = V<ll>;using vii = V<int>;using vvll = V<vll>;using vvii = V< V<int> >;using PII = P<int, int>;using PLL = P<ll, ll>;#define RevREP(i,n,a) for(ll i=n;i>a;i--) // (a,n]#define REP(i,a,n) for(ll i=a;i<n;i++) // [a,n)#define rep(i, n) REP(i,0,n)#define ALL(v) v.begin(),v.end()#define eb emplace_back#define pb push_backtemplate < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }#define DEBUG_VLL(vec) for(int sz=0;sz<int(vec.size());sz++) std::cerr<<vec[sz]<<(sz==int(vec.size())-1?'\n':' ');const long long MOD = 1000000007;const long long HIGHINF = (long long)1e18;const int INF = (int)1e9;using PLI = P<ll, int>;int main() {cin.tie(0);ios::sync_with_stdio(false);int t, n, m; cin >> t >> n >> m;V< V<PII> > edges(n);rep(i, m) {int u, v, w; cin >> u >> v >> w;u--, v--;edges[u].eb(PII(v, w));if (t == 0) edges[v].eb(PII(u, w));}ll ans = HIGHINF;rep(i, n) {for (PII to: edges[i]) {auto [ton, tow] = to;vll dist(n, HIGHINF);priority_queue<PLI> pq;pq.push(PLI(0, ton));while (pq.size() > 0) {PLI q = pq.top(); pq.pop();if (dist[q.second] < -q.first) continue;dist[q.second] = -q.first;for (PII e: edges[q.second]) {if (dist[e.first] < ll(-q.first) + e.second) continue;if ((q.second == i and e.first == ton) or (t == 0 and q.second == ton and e.first == i)) continue;pq.push(PLI(-(ll(-q.first) + e.second), e.first));}}if (dist[i] < HIGHINF) chmin(ans, dist[i] + tow);}}if (ans == HIGHINF) ans = -1;cout << ans << '\n';return 0;}