Submission #154051

#TimeUsernameProblemLanguageResultExecution timeMemory
154051gratus907두 로봇 (KOI18_robot)C++17
59 / 100
1071 ms9080 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #define ll long long #define eps 1e-7 #define all(x) ((x).begin()),((x).end()) #define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; typedef pair <int, int> pii; int n, a, b; vector <pii> graph[101010]; vector <int> stk; bool visit[101010]; int dist[101010]; int main() { cin >> n; cin >> a >> b; for (int i = 1; i<n; i++) { int u, v, w; cin >> u >> v >> w; graph[u].push_back({v,w}); graph[v].push_back({u,w}); } stk.push_back(a); visit[a] = 1; dist[a] = 0; while(!stk.empty()) { int x = stk.back(); if (x==b) break; bool flag = false; for (auto it:graph[x]) { if (!visit[it.first]) { flag = true; visit[it.first] = 1; dist[it.first] = (dist[x] + it.second); stk.push_back(it.first); break; } } if (!flag) stk.pop_back(); } int mm = 0; int s = stk.size(); for (int i = 1; i<s; i++) mm = max(mm, dist[stk[i]]-dist[stk[i-1]]); cout << dist[stk.back()]-mm; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...