Submission #851158

#TimeUsernameProblemLanguageResultExecution timeMemory
851158pakapuCheap flights (LMIO18_pigus_skrydziai)C++17
0 / 100
78 ms21416 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int ans = 0; int curr_flag = 0; vector<int> cost; vector<int> calculated; vector<vector<pair<int, int>>> g; int dfs(int u, int depth) { if(depth >= 2) { return 0; } if(depth == 1) { for(auto v : g[u]) { if(calculated[v.first] != curr_flag) { continue; } //cout << v.first << ' ' << u << '\n'; //cout << cost[v.first] << ' ' << cost[u] << ' ' << v.second << '\n'; ans = max(ans, cost[v.first] + cost[u] + v.second); } return 0; } int curr = 0; for(auto v : g[u]) { cost[v.first] = v.second; calculated[v.first] = curr_flag; curr += v.second; dfs(v.first, depth + 1); } return curr; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; cost = vector<int>(n); calculated = vector<int>(n); g = vector<vector<pair<int, int>>>(n); for(int i = 0; i < m; i++) { int from, to, w; cin >> from >> to >> w; from--; to--; g[from].push_back(make_pair(to, w)); g[to].push_back(make_pair(from, w)); } ans = 0; for(int i = 0; i < n; i++) { curr_flag = i; int curr = dfs(i, 0); ans = max(ans, curr); } cout << ans << '\n'; return 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...