백준 15971 두 로봇

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

만나기 위해 움직여야하는 최단거리지만, 결국 통로 하나를 사이에 두고 이어진 방에서 만나는 것. 

그래서 두 로봇 사이의 거리의 합에서 제일 긴 통로의 길이를 빼준 게 답이 된다. 

spot(정점), tot(거쳐온 거리의 합), ma(지금까지 제일 긴 통로 길이)로 구조체 만들어서 bfs 돌렸다.

 

#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
typedef struct a
{
    int spot;
    int tot;
    int ma;
}type;
typedef struct b
{
    int con;
    int len;
}one;
using namespace std;
vector<one> V[100005];
queue<type> Q;
int visit[100005];
int n,s,e;
int main()
{
    cin >> n >> s >> e;
    for(int i=0;i<n-1;i++)
    {
        int a,b,l;
        cin >> a >> b>>l;
        V[a].push_back({b,l});
        V[b].push_back({a,l});
    }
    visit[s]=1;
    Q.push({s,0,0});
    int ans;
    while(!Q.empty())
    {
        type k=Q.front();
        Q.pop();
        int p=k.spot;
        if(p==e)
        {
            ans=k.tot-k.ma;
            break;
        }
        for(auto it=V[p].begin();it!=V[p].end();++it)
        {
            if(visit[it->con]==0)
            {
                visit[it->con]=1;
                int M=k.ma;
                if(it->len>M) M=it->len;
                Q.push({it->con,k.tot+it->len,M});
            }
        }
    }
    cout << ans;
}