結果
問題 |
No.1320 Two Type Min Cost Cycle
|
ユーザー |
|
提出日時 | 2022-03-13 03:53:39 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 552 ms / 2,000 ms |
コード長 | 1,507 bytes |
コンパイル時間 | 3,203 ms |
コンパイル使用メモリ | 262,804 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-17 12:52:42 |
合計ジャッジ時間 | 7,300 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#include<bits/stdc++.h> using namespace std; using pl=pair<long long,long long>; using Graph=vector<vector<long long>>; long long shortest_cycle(long long n,long long m,vector<long long> &u,vector<long long> &v,vector<long long> &w,bool isdirected){ long long res=8e18; Graph g(n); vector<pl> vp; for(int i=0;i<m;i++){ g[u[i]].push_back(i); if(!isdirected){ g[v[i]].push_back(i); } vp.push_back({w[i],i}); } sort(vp.begin(),vp.end()); for(int ec=0;ec<m;ec++){ long long eid=vp[ec].second; if(w[eid]>=res){break;} priority_queue<pl,vector<pl>,greater<pl>> pq; pq.push({w[eid],v[eid]}); vector<long long> d(n,8e18); d[v[eid]]=w[eid]; while(!pq.empty()){ pl od=pq.top();pq.pop(); if(od.first>=res){break;} if(od.second==u[eid]){res=min(res,od.first);break;} for(auto &nx : g[od.second]){ if(nx==eid){continue;} long long nv=(u[nx]^v[nx]^od.second); long long nd=od.first+w[nx]; if(d[nv]>nd){ d[nv]=nd; pq.push({nd,nv}); } } } } if(res>7e18){res=-1;} return res; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; bool isdirected; if(t==0){isdirected=false;} else{isdirected=true;} long long n,m; cin >> n >> m; vector<long long> u(m),v(m),w(m); for(int i=0;i<m;i++){ cin >> u[i] >> v[i] >> w[i]; u[i]--;v[i]--; } cout << shortest_cycle(n,m,u,v,w,isdirected) << '\n'; return 0; }