Submission #219502

#TimeUsernameProblemLanguageResultExecution timeMemory
219502quocnguyen1012Cheap flights (LMIO18_pigus_skrydziai)C++14
100 / 100
1561 ms89544 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef pair<int, int> ii; const int maxn = 3e5 + 5; map<ii, int> cost; int N, M; vector<ii> adj[maxn]; signed main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("A.INP", "r", stdin); freopen("A.OUT", "w", stdout); #endif // LOCAL cin >> N >> M; ll res = 0; while(M--){ int u, v, w; cin >> u >> v >> w; cost[mp(u, v)] = cost[mp(v, u)] = w; adj[u].eb(w, v); adj[v].eb(w, u); } for(int i = 1; i <= N; ++i){ sort(adj[i].rbegin(), adj[i].rend()); ll sum = 0; for(auto & it : adj[i]) sum += it.fi; if(adj[i].size() >= 2 && cost[mp(adj[i][0].se, adj[i][1].se)]) res = max(res, 1ll * adj[i][0].fi + adj[i][1].fi + cost[mp(adj[i][0].se, adj[i][1].se)]); res = max(res, sum); } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...