제출 #382159

#제출 시각아이디문제언어결과실행 시간메모리
382159MohamedAhmed04Cheap flights (LMIO18_pigus_skrydziai)C++14
53 / 100
325 ms50924 KiB
#include <bits/stdc++.h> using namespace std ; const int MAX = 3e5 + 10 ; int vis[MAX] , mark[MAX] , dep[MAX] ; int n , m ; vector< vector< pair<int , int> > >adj(MAX) ; long long ans = 0ll ; void dfs(int node , long long x , long long y) { vis[node] = mark[node] = 1 ; long long sum = 0 ; for(auto &child : adj[node]) { int to = child.first ; sum += child.second ; if(vis[to]) { if(mark[to] && dep[to] == dep[node] - 2) ans = max(ans , x + y + child.second) ; continue ; } dep[to] = dep[node] + 1 ; dfs(to , y , child.second) ; } ans = max(ans , sum) ; mark[node] = 0 ; } int main() { ios_base::sync_with_stdio(0) ; cin.tie(0) ; cin>>n>>m ; for(int i = 0 ; i < m ; ++i) { int x , y , z ; cin>>x>>y>>z ; adj[x].emplace_back(y , z) ; adj[y].emplace_back(x , z) ; } for(int i = 1 ; i <= n ; ++i) { if(!vis[i]) dfs(i , 0 , 0) ; } return cout<<ans<<"\n" , 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...