Submission #154052

#	Time	Username	Problem	Language	Result	Execution time	Memory
154052		gratus907	두 로봇 (KOI18_robot)	C++17	59 / 100	1069 ms	9120 KiB

robot

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#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()
{
  	usecppio
    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;
}

• Subtask 1: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41