結果

問題 No.1320 Two Type Min Cost Cycle
ユーザー vjudge1
提出日時 2025-10-01 20:26:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 243 ms / 2,000 ms
コード長 1,991 bytes
コンパイル時間 1,811 ms
コンパイル使用メモリ 171,188 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-01 20:26:43
合計ジャッジ時間 6,144 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4002,inf=1e18;
int t,n,m,u[N],v[N],w[N],f[N];
bool vis[N],pa[N];
vector<int> x[N],y[N],z[N];
struct node{
	int x,id,ba;
	friend bool operator <(const node &x,const node &y){
		if(x.x!=y.x) return x.x>y.x;
		else return x.id>y.id;
	}
};
priority_queue<node> p;
void dij(int s){
    for(int i=1;i<=n;i++) vis[i]=0,f[i]=inf;
    for(int i=1;i<=m;i++)pa[i]=0;
    p.push((node){0,s});
    f[s]=0;
    while(!p.empty()){
        int op=p.top().id,sum=p.top().ba;
        p.pop();
        if(vis[op])continue;
        vis[op]=1;
        pa[sum]=1;
        for(int i=0;i<x[op].size();i++){
            if(y[op][i]+f[op]<f[x[op][i]]){
                f[x[op][i]]=y[op][i]+f[op];
                p.push((node){f[x[op][i]],x[op][i],z[op][i]});
            }
        }
    }
    return;
}
signed main(){
    cin>>t>>n>>m;
    if(t==0){
        for(int i=1;i<=m;i++){
            cin>>u[i]>>v[i]>>w[i];
            x[u[i]].push_back(v[i]);
            x[v[i]].push_back(u[i]);
            y[u[i]].push_back(w[i]);
            y[v[i]].push_back(w[i]);
            z[u[i]].push_back(i);
            z[v[i]].push_back(i);
        }
        int ans=inf;
        for(int i=1;i<=n;i++){
            dij(i);
            for(int j=1;j<=m;j++){
                if(pa[j]==0){
                    ans=min(ans,f[u[j]]+f[v[j]]+w[j]);
                }
            }
        }
        if(ans==inf) ans=-1;
        cout<<ans<<endl;
    }
    else {
        for(int i=1;i<=m;i++){
            cin>>u[i]>>v[i]>>w[i];
            x[u[i]].push_back(v[i]);
            y[u[i]].push_back(w[i]);
            z[u[i]].push_back(i);
        }
        int ans=inf;
        for(int i=1;i<=n;i++){
            dij(i);
            for(int j=1;j<=m;j++){
                if(v[j]==i){
                    ans=min(ans,f[u[j]]+w[j]);
                }
            }
        }
        if(ans==inf) ans=-1;
        cout<<ans<<endl;
    }
    return 0;
}
/*
*/
0