結果

問題 No.1320 Two Type Min Cost Cycle
コンテスト
ユーザー vjudge1
提出日時 2025-09-30 17:56:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 989 bytes
コンパイル時間 3,658 ms
コンパイル使用メモリ 283,980 KB
実行使用メモリ 34,580 KB
最終ジャッジ日時 2025-09-30 17:56:47
合計ジャッジ時間 5,736 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2010,inf=1e18;
int T,n,m,ans=inf,u,v,w,p,pp,d[N],dis[N][N],vis[N];
struct S{int v,w;bool friend operator <(const S a,const S b){return a.w>b.w;}}Q;
vector<int> g[N];
priority_queue<S> q;
void dij(int s){
	for(int i=1;i<=n;i++)d[i]=1e15;
	d[s]=0,q.push((S){s,0});
	while(!q.empty()){
		Q=q.top();q.pop();
		if(vis[Q.v])continue;
		vis[Q.v]=1;
		for(int y:g[Q.v]){
			w=dis[Q.v][y];
			if((d[Q.v]+w<d[y])&&w)d[y]=d[Q.v]+w,q.push((S){y,d[y]});
		}
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		if(T==1)dis[u][v]=w,g[u].push_back(v);
		else dis[u][v]=dis[v][u]=w,g[u].push_back(v),g[v].push_back(u);
	}
	for(int x=1;x<=n;x++)for(int y=1;y<=n;y++)if(dis[x][y]){
		p=dis[x][y],pp=dis[y][x],dis[x][y]=dis[y][x]=0;
		dij(y);
		ans=min(ans,d[x]+p),dis[x][y]=p,dis[y][x]=pp;
	}
	if(ans>1e14)cout<<"-1\n";
	else cout<<ans<<"\n";
	return 0;
}
0