Submission #600707

#TimeUsernameProblemLanguageResultExecution timeMemory
600707narvaloFerries (NOI13_ferries)C++17
0 / 40
145 ms23372 KiB
#include <bits/stdc++.h> using namespace std; int ferries(int n , int m , vector<int> a , vector<int> b , vector<int> c) { vector<vector<pair<int , int>>> adj(n); for (int i = 0 ; i < m ; i++) { a[i] -= 1 , b[i] -= 1; adj[a[i]].emplace_back(b[i] , c[i]); adj[b[i]].emplace_back(a[i] , c[i]); } sort(c.begin() , c.end()); if (m == n - 1) { int ans = -1; function<void(int , int , int)> Dfs = [&](int cur , int pre , int depth) { if (cur == n - 1) { ans = depth; } for (auto x : adj[cur]) { if (x.first == pre) continue; Dfs(x.first , cur , depth + 1); } return ; }; Dfs(0 , -1 , 0); int res = 0; for (int i = 0 ; i < ans ; i += 1) { res += c[i]; } return res; } else { int res = 0; for (int i = 0 ; i < 2 ; i += 1) { res += c[i]; } return res; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n , m; cin >> n >> m; vector<int> a(m) , b(m) , c(m); for (int i = 0 ; i < m ; i += 1) { cin >> a[i] >> b[i] >> c[i]; } cout << ferries(n , m , a , b , c) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...