[BJ 15971] 두 로봇
2019. 7. 24. 05:41ㆍComputerScience/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 |