This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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}];
}
};
const int mxN = (int)3e5;
set<int> adj[mxN];
weight w;
void solve() {
int N, E; cin >> N >> E;
vector<ll> ws(N);
for(int i = 0; i < E; i++) {
int U, V, P;
cin >> U >> V >> P;
--U, --V;
ws[U] += P;
ws[V] += P;
adj[U].insert(V);
adj[V].insert(U);
w.setW(U, V, P);
}
ll ans = *max_element(ws.begin(), ws.end());
set<set<int>> cycles;
for(int u = 0; u < N; u++) {
for(int v : adj[u]) {
for(int r : adj[v]) {
for(int j : adj[r]) if(j == u) {
set<int> cycle = {u, v, r};
if(cycles.find(cycle) == cycles.end()) {
ans = max(ans, (ll)w.getW(u,v) + (ll)w.getW(v,r) + (ll)w.getW(u,r));
cycles.insert(cycle);
}
}
}
}
}
cout << ans << '\n';
// for(int i = 0; i < N; i++) {
// set<int> visited;
// for(int v : adj[i]) {
// for(int n : visited) {
// if(adj[v].find(n) != adj[v].end()) {
// set<int> cycle = {i, v, n};
// if(cycles.find(cycle) == cycles.end()) {
// ans = max(ans, (ll)w.getW(i,v) + (ll)w.getW(v,n) + (ll)w.getW(i,n));
// cycles.insert(cycle);
// }
// }
// }
// visited.insert(v);
// }
// }
// 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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |