Submission #1841212

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define Rep(i, n) For(i, 0, (n))

const int inf = 999999999;
const int mod = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int d[310][310];

int main(){
	int n, m; cin >> n >> m;
	vector<P> tonari;
	Rep(i, 310) Rep(j, 310) d[i][j] = inf;
	Rep(i, 310) d[i][i] = 0;
	Rep(i, m){
		int u, v, l;
		cin >> u >> v >> l;
		u--, v--;
		if(u == 0){
			tonari.push_back(P(v, l));
		}else if(v == 0){
			tonari.push_back(P(u, l));
		}else{
			d[u][v] = l; d[v][u] = l;
		}
	}
	Rep(k, n) Rep(i, n) Rep(j, n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	int ans = inf;
	for(auto u : tonari){
		for(auto v : tonari){
			if(u.first == v.first) continue;
			ans = min(ans, u.second + v.second + d[u.first][v.first]);
		}
	}
	if(ans == inf) ans = -1;
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result