# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
304751 | computerbox | Cheap flights (LMIO18_pigus_skrydziai) | C++14 | 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>
#define FLASH ios_base::sync_with_stdio(0);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";
using namespace std;
set<pair<ll,ll> >adj[300010];
void make_set(ll n)
{
for(ll i=1;i<=n;i++){par[i]=i;rankk[i]=1;}
}
ll findd(ll v)
{
while(par[v]!=v)
{
par[v]=par[par[v]];
v=par[v];
}
return v;
}
void make_union(ll a,ll b)
{
a=findd(a);
b=findd(b);
if(a!=b)
{
if(rankk[a]>rankk[b])swap(a,b);
rankk[b]+=rankk[a];
par[a]=par[b];
}
}
struct edge
{
ll x,y,z;
};
vector<edge>massiv;
ll sorthus(edge a,edge b)
{
return a.z>b.z;
}
ll n,m;
int main(){
FLASH;
cin>>n>>m;
for(ll i=1;i<=m;i++)
{
ll x,y,z;
cin>>x>>y>>z;
adj[x].insert(mp(y,z));
adj[y].insert(mp(x,z));
}
ll maxx=0;
ll summ=0;
for(ll i=1;i<=n;i++)
{
summ=0;
for(auto j:adj[i])summ+=j.second;
maxx=max(maxx,summ);
}
for(ll i=1;i<=n;i++)
{
for(auto j:adj[i])
{
for(auto j1:adj[j.first])
{
ll y=j1.first;
if(y==i)continue;
auto yy=j1.first;
auto ch=adj[yy].lower_bound(mp(i,0));
if(ch!=adj[yy].end() && (*ch).first==i)
{
maxx=max(maxx,j.second+j1.second+(*ch).second);
}
}
}
}
cout<<maxx<<endl;
return 0;
}