Submission #634826

#	Time	Username	Problem	Language	Result	Execution time	Memory
634826		mrkhan2000	Cheap flights (LMIO18_pigus_skrydziai)	C++17	100 / 100	1681 ms	37276 KiB

pigus_skrydziai

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;

struct weight {
	map<pair<int,int>, int> w;
	void setW(int u, int v, int p) {
		if(u > v) swap(u,v);
		w[{u,v}] = p;
	}
	int getW(int u, int v) {
		if(u > v) swap(u, v);
		return w[{u,v}];
	}
	int count(int u, int v) {
		if(u > v) swap(u, v);
		return w.count({u,v});
	}
};

void solve() {
	int N, E; cin >> N >> E;
	vector<int> adj[N];
	weight w;
	for(int i = 0; i < E; i++) {
		int U, V, P;
		cin >> U >> V >> P;
		--U, --V;
		adj[U].push_back(V);
		adj[V].push_back(U);
		w.setW(U, V, P);
	}
	ll ans = 0LL;
	for(int u = 0; u < N; u++) {
		ll tmp = adj[u].size() ? (ll)w.getW(u, adj[u][0]) : 0LL;
		for(int j = 0; j < (int)adj[u].size() - 1; j++) {
			int v = adj[u][j], r = adj[u][j + 1];
			tmp += (ll)w.getW(u, r);
			if(w.count(v, r)) {
				ans = max(ans, (ll)w.getW(u,v) + (ll)w.getW(v,r) + (ll)w.getW(u,r));
			}
		}
		ans = max(ans, tmp);
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int test_cases = 1;
	// cin >> test_cases;
	for(int test_case = 1; test_case <= test_cases; test_case++) {
		// cout << "Case #" << test_case << ": ";
		solve();
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 25 / 25
• Subtask 3: 16 / 16
• Subtask 4: 47 / 47