Submission #43534742

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const ll MAXN = 410,INF = 1e18;
void tomin(ll& x,ll y){x=min(x,y);}

int n,m;
ll e[MAXN][MAXN],ans = INF;
int tag[MAXN][MAXN];

int ban[MAXN];
ll dis[MAXN],vis[MAXN],pre[MAXN];

int lab[MAXN];
vector<int>t[MAXN];

void dfs(int u){
	for(auto v:t[u])lab[v] = lab[u],dfs(v);
}

ll dij(int x){
	memset(tag,0,sizeof tag);
	rep(i,1,n)dis[i] = INF,vis[i] = pre[i] = 0;
	dis[x] = 0;
	while(1){
		int u = 0;
		rep(i,1,n)if(!vis[i] && (!u || dis[u] > dis[i]))u = i;
		if(!u)break;
		vis[u] = 1;
		rep(v,1,n)if(!ban[v] && dis[v] > dis[u] + e[u][v]){
			tag[pre[v]][v] = tag[v][pre[v]] = 0;

			dis[v] = dis[u] + e[u][v];
			pre[v] = u;

			tag[pre[v]][v] = tag[v][pre[v]] = 1;
		}
	}

	rep(i,1,n)t[i].clear();
	rep(i,1,n)if(pre[i])t[pre[i]].push_back(i);

	lab[x] = x;
	for(auto u:t[x]){
		lab[u] = u;
		dfs(u);
	}

	ll cyc = INF;

	rep(u,1,n)rep(v,1,n)if(!tag[u][v] && lab[u] != lab[v])tomin(cyc,dis[u] + dis[v] + e[u][v]);

	return cyc;
}

int inc[MAXN];

void solve(int x){
	ll cyc = dij(x);

	if(cyc == INF)return;

	memset(inc,0,sizeof inc);

	int a = 0,b = 0;

	rep(u,1,n)rep(v,1,n)if(!tag[u][v] && lab[u] != lab[v] && dis[u] + dis[v] + e[u][v] == cyc){
		for(int p=u;p;p=pre[p])inc[p]=1;
		for(int p=v;p;p=pre[p])inc[p]=1;

		if(u!=x && v!=x)a = lab[u],b = lab[v];
		else{
			if(v==x)swap(u,v);
			a = v,b = lab[v];
		}
		goto END;
	}

	END : ;
	
	assert(a && b);

	rep(u,1,n)if(!inc[u])tomin(ans,cyc + e[x][u]); 
	
	ban[a] = 1;
	tomin(ans,dij(x) + e[x][a]);
	ban[a] = 0;

	ban[b] = 1;
	tomin(ans,dij(x) + e[x][b]);
	ban[b]= 0;
}	

int main(){
	cin>>n>>m;
	rep(i,1,n)rep(j,1,n)e[i][j] = INF;
	rep(i,1,m){
		int u,v,w;cin>>u>>v>>w;
		e[u][v] = e[v][u] = w;
	}
	
	rep(i,1,n){
		solve(i);
	}

	if(ans==INF)cout<<"-1\n";
	else cout<<ans<<endl;

    return 0;
}

Submission Info

Judge Result