Submission #851159

#TimeUsernameProblemLanguageResultExecution timeMemory
851159pakapuCheap flights (LMIO18_pigus_skrydziai)C++17
37 / 100
3043 ms32196 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int ans = 0; vector<int> cost; vector<int> calculated; vector<vector<pair<int, int>>> g; int dfs(int u, int depth, int flag) { if(depth >= 2) { return 0; } if(depth == 1) { for(auto v : g[u]) { if(calculated[v.first] == flag) { //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] = flag; curr += v.second; dfs(v.first, depth + 1, flag); } 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, -1); 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++) { int curr = dfs(i, 0, i + 1); 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...