# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
498238 | Kipras | 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>
typedef long long ll;
using namespace std;
const int maxN = 1e5*3+1;
int n, m;
vector<int> adj[maxN];
int val[maxN][maxN];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(nullptr);
for(int i = 0; i < maxN; i++)for(int x = 0; x < maxN; x++)val[i][x]=-1;
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b, c;
cin>>a>>b>>c;
adj[a].push_back(b);
adj[b].push_back(a);
val[a][b]=c;
val[b][a]=c;
}
ll ans=0;
for(int i = 1; i <= n; i++){
ll temp=0;
for(auto x : adj[i]){
temp+=val[i][x];
}
ans=max(ans, temp);
}
for(int i = 1; i <= n; i++){
for(int x = 0; x < adj[i].size()-1; x++){
ll temp=0;
if(val[adj[i][x]][adj[i][x+1]]!=-1){
temp=val[adj[i][x]][adj[i][x+1]+val[i][adj[i][x]]+val[i][adj[i][x+1]];
}else continue;
ans=max(ans, temp);
}
}
cout<<ans;
return 0;
}