[BJ 15971] 두 로봇

2019. 7. 24. 05:41ComputerScience/Algorithm

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

 

15971번: 두 로봇

입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과 출력의 예에서 예제 입력 1을 참고).

www.acmicpc.net

쉬운 문제들도 코드를 더 직관적이고 깔끔하게 푸는 연습이 너무 부족한듯하다

 

 

한점을 출발점, 한 점을 목적지로 설정하고 dfs로 목적지에 도착하면 경로를 백트랙하면

경로까지의 거리를 구하고 그중 가장큰값을 빼면된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;
#define pii pair<int,int>
int n,a, b,flag=0,weight =0,m=0;
vector<int> visit;
vector<vector<pii>> vi;
vector<int> path;
void dfs(int N) {
if (visit[N]) return;
visit[N] = 1;
if (N == b) {
flag = 1;
return;
}
for (int i = 0; i < vi[N].size(); i++) {
dfs(vi[N][i].first);
if (flag) {
weight += vi[N][i].second;
m = max(m, vi[N][i].second);
break;
}
}
}
int main() {
cin >> n >> a >> b;
visit.assign(n + 1, 0);
vi.resize(n + 1);
int x, y,w;
for (int i = 0; i < n - 1; i++) {
cin >> x >> y >> w;
vi[x].push_back(pii(y,w));
vi[y].push_back(pii(x,w));
}
dfs(a);
cout << weight - m;
}

 

'ComputerScience > Algorithm' 카테고리의 다른 글

[BOJ2580] 스도쿠  (0) 2020.10.28
[BJ15975] 화살표 그리기  (0) 2019.07.25
[BJ15973] 두 박스 .  (0) 2019.07.24