結果

問題 No.1320 Two Type Min Cost Cycle
ユーザー vjudge1
提出日時 2025-09-30 12:38:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 114 ms / 2,000 ms
コード長 1,233 bytes
コンパイル時間 1,752 ms
コンパイル使用メモリ 170,500 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-30 12:38:47
合計ジャッジ時間 5,449 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define lint __int128
#define int long long
#define Il inline
#define fi first
#define se second
#define vec vector
#define pb push_back
#define IT ::iterator
#define p_q priority_queue

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const int N=2e3,Inf=1e18;
const db eps=1e-9,pi=acos(-1.0);

mt19937 rnd(time(0));
Il int rint(int l,int r){return rnd()%(r-l+1)+l;}

int n,m,ex[N+5],ey[N+5],ew[N+5],tmp,dis[N+5],ans=Inf;
vec<pii>v[N+5];
bool vis[N+5];
struct Nodj{int ds,ps;Il bool operator <(const Nodj &s)const{return ds>s.ds;}};
p_q<Nodj>dj;

Il void dijk(int id,int s){
    dj.push({0,s});for(int i=1;i<=n;i++)dis[i]=(i^s?Inf:0),vis[i]=0;
    while(!dj.empty()){
        int fq=dj.top().ps;dj.pop();if(vis[fq])continue;
        vis[fq]=1;for(pii i:v[fq])if((i.se^id)&&dis[i.fi]>dis[fq]+ew[i.se])dj.push({dis[i.fi]=dis[fq]+ew[i.se],i.fi});
    }
    return;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>tmp>>n>>m;for(int i=1;i<=m;i++){cin>>ex[i]>>ey[i]>>ew[i];v[ex[i]].pb({ey[i],i});if(!tmp)v[ey[i]].pb({ex[i],i});}
    for(int i=1;i<=m;i++)dijk(i,ey[i]),ans=min(ans,dis[ex[i]]+ew[i]);
    cout<<(ans^Inf?ans:-1);
    return 0;
}
0