# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
590824 | Kipras | Cheap flights (LMIO18_pigus_skrydziai) | C++17 | 0 ms | 0 KiB |
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>
typedef long long ll;
using namespace std;
const ll maxN = 3e5+10;
ll n, m;
ll v[maxN]={0};
vector<ll> adj[maxN];
map<pair<ll, ll>, ll> a;
int main()
{
ios_base::sync_with_stdio(0);cin.tie(nullptr);
cin>>n>>m;
for(int i = 0; i < m; i++){
ll aa, bb, cc;
cin>>aa>>bb>>cc;
v[aa]+=cc;
v[bb]+=cc;
adj[aa].push_back(bb);
adj[bb].push_back(aa);
a[{aa, bb}]=cc;
a[{bb, aa}]=cc;
}
ll res=0;
for(int i = 1; i <= n; i++){
res=max(res, v[i]);
for(ll x = 0; x < (ll)(adj[i].size())-1; x++){
ll v=adj[i][x], vv=adj[i][x+1];
if(a.count({i, x}>0)){
res=max(res, a[{i, v}]+a[{i, vv}]+a[{v, vv}]);
}
}
}
cout<<res;
return 0;
}