두 로봇 - 15971

//15971 - 두 로봇
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
#define INF 1000000000
 
int N, S, E;
vector<vector<pair<int, int>>> adj;
 
void init()
{
    cin >> N >> S >> E;
    adj = vector<vector<pair<int, int>>>(N+1);
    int x, y, r;
    for(int i = 0; i<N-1; ++i)
    {
        cin >> x >> y >> r;
        adj[x].push_back(make_pair(y, r));
        adj[y].push_back(make_pair(x, r));
    }
}
 
void dijkstra()
{
    priority_queue<pair<int, int>> pq;
    vector<int> dist(N+1, INF);
    vector<int> parent(N+1);
    vector<int> length(N+1);
 
    pq.push(make_pair(0, S));
    dist[S] = 0;
    parent[S] = S;
 
    while(!pq.empty())
    {
        int here = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
 
        if(dist[here] < cost) continue;
 
        for(int i = 0; i<adj[here].size(); ++i)
        {
            int there = adj[here][i].first;
            int c = adj[here][i].second;
            if(cost + c < dist[there])
            {
                dist[there] = cost + c;
                parent[there] = here;
                length[there] = c;
                pq.push(make_pair(-c-cost, there));
            }
        }
    }
 
    int u = 0;
    for(int i = E; i != parent[i]; i = parent[i])
        u = max(u, length[i]);
    cout << dist[E] - u;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    dijkstra();
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/15971

15971번: 두 로봇

 

 

 

 

 

 

두 로봇

두 지점 사이에 최단거리를 구하고, 경로중 가장 큰 통로를 최단거리에서 빼주었습니다.