Submission #392625

---

Source Code Expand

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;

typedef pair<int, int> pi;
typedef pair<int,pair<int, int>> pii;
int N, M;
int u, v,l;
int adj[300][300];

int main(void){
	for (int i = 0; i < 300; i++)for (int j = 0; j < 300; j++)if (i != j)adj[i][j] = 100000000;
	cin >> N >> M;

	for (int i = 0; i < M; i++){
		cin >> u >> v>>l;
		u--; v--;
		adj[u][v]
			= adj[v][u] = l;
	}
	for (int k = 1; k < N; k++)
		for (int i = 1; i < N; i++)
			for (int j = 1; j < N; j++)adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
	int res = 100000000;
	for (int i = 1; i < N; i++)
		for (int j = 1; j < N; j++)
			if (i != j)res = min(res, adj[0][i] + adj[i][j] + adj[j][0]);
	if (res >= 100000000)cout << -1 << endl;
	else cout<<res << endl;

	return(0);
}

Submission Info

Judge Result