Submission #44974527

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define pb(a) push_back(a)
#define MAX(a, b) ((a < b)?b:a)
#define MIN(a, b) ((a > b)?b:a)
#define lcm(a, b) (a / gcd(a, b) * b) // 最小公倍数

typedef long long int ll;
typedef unsigned long long int ull;
typedef unsigned int uint;
using namespace std;
// -------------------------------------

class Node;

class Connect {
	public:
	Connect(Node* _node, int _cost) {
		node = _node;
		cost = _cost;
	}

	Node* node;
	int cost;
};

class Node {
	public:
	Node(int _id) {
		id = _id;
	} 
	int id;
	vector<Connect> list;
};

int N, M;
Node* node_list[10 + 1];



int solve(int from, int to, vector<int> path) {
	if ( from == to ) return 0;

	int cost_max = -1;
	path.pb(from);
	for (auto con : node_list[from]->list) {
		int next_node_id = con.node->id;
		if (count(path.begin(), path.end(), next_node_id)) break; // 次に行くところに行ったことがあったらもう行かない

		try {
			int cost = solve(next_node_id, to, path) + con.cost;
			if (cost_max < cost) cost_max = cost;
		} catch (...) {
			// この先のルートはないので何もしない
		}
	}

	if ( cost_max == -1 ) throw 0; // 行き止まりだった場合はこのルートを使わないようにする

	return cost_max;
}

int main() {
	cin >> N >> M;

	rep(i, N) {
		node_list[i + 1] = new Node(i + 1);
	}

	rep(i, M) {
		int a, b, c;
		cin >> a >> b >> c;
		
		node_list[a]->list.pb(Connect(node_list[b], c));
		node_list[b]->list.pb(Connect(node_list[a], c));
	}

	vector<int> path_zero;
	int ans = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			try {
				int cost = solve(i, j, path_zero);
				if ( ans < cost ) ans = cost;
			} catch(...) {
				// このルートはたどり着かない
			}
		}
	}

	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result