ABC022 C - Blue Bird

C - Blue Bird

概要

N頂点M辺の無向グラフについて、頂点0から少なくとも1つの辺を通り、かつ同じ辺を通らずに再び頂点0に戻る経路のうち、最短の長さを答えよ。

制約

1 ≦ N ≦ 300

方針

頂点0と０を含む辺を除いたグラフでワーシャルフロイドする。
その後、0と隣接している2頂点x, yについて０ -> x -> y -> ０の経路長をx, yについて全通り比べる。
O(N^3)なので間に合う。

感想

愚直に再帰させるとTLE
Submission #6943593 - AtCoder Beginner Contest 022

解答

Submission #6943674 - AtCoder Beginner Contest 022

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<int, ll> pil;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, M;
	cin >> N >> M;
 
	ll INF = 1e15;
	vector<vector<ll>> dist(N, vector<ll>(N, INF));
	vector<pil> neigh;
	rep(i, N) dist[i][i] = 0;
	rep(i, M){
		int u, v, l;
		cin >> u >> v >> l;
		u--; v--;
		if(u == 0) {
			neigh.push_back({v, l});
			continue;
		}
 
		if(v == 0){
			neigh.push_back({u, l});
			continue;
		}
 
		dist[u][v] = l;
		dist[v][u] = l;
	}
 
	rep(k, N) rep(i, N) rep(j, N) {
		dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
	}
 
	// rep(i, N) rep(j, N) cout << dist[i][j] << (j == N - 1 ? "\n" : " ");
 
	ll ans = INF;
	for(pil x : neigh){
		for(pil y : neigh){
			if(x.first == y.first) continue;
			ans = min(ans, x.second + dist[x.first][y.first] + y.second);
		}
	}
 
	cout << (ans == INF ? -1 : ans) << endl;
 
}