1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
특정 노드로 이동했다가 돌아와야 한다는 점을 추가해야 하는 최장/최단 거리 탐색 문제이다.
다익스트라 알고리즘의 동작에 대하여 잘 모른다면 [링크] 를 우선 참조하자
노드 A에서 출발했다 가정했을 때, 이미 방문한 노드 그룹에 대한 처리와, 이후에 필요할 다른 임의의 노드에서 A 노드로 왔다가 임의의 노드로 돌아가는 (= A에서 출발해서 임의의 노드로 이동하는) 값을 이용하기 위하여 아래와 같이 memo 변수를 추가로 이용했다.
그 점을 제외하면 기본 다익스트라 문제와 완전히 동일하다.
struct town {
vector<pair<int, int>> wayCost;
vector<int> cost;
vector<int> memo;
};
물론 굳이 돌아오는 경로에 대하여 메모하지 않더라도 결국 모든 도시에서의 다익스트라 경로를 구하기 때문에 따로 메모를 할 필요는 없다.
그런데 그렇게 하면 위쪽처럼 못하고 아래쪽처럼 해야 하는데 취향의 차이로 메모 변수를 사용했다.
if (towns[i].cost[targetTown] + towns[i].memo[targetTown] > max)
max = towns[i].cost[targetTown] + towns[i].memo[targetTown];
///// vs
if (towns[i].cost[targetTown] + towns[targetTown].cost[i] > max)
max = towns[i].cost[targetTown] + towns[targetTown].cost[i];code
GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지
알고리즘 온라인 저지. Contribute to YoungWoo93/algorithmOnlineJudge development by creating an account on GitHub.
github.com
'알고리즘 온라인 저지 > BOJ' 카테고리의 다른 글
| BOJ 1339 단어 수학 (0) | 2022.01.30 |
|---|---|
| BOJ 2178 미로 탐색 (0) | 2022.01.28 |
| BOJ 1202번 보석 도둑 (0) | 2022.01.18 |
| BOJ 2014 소수의 곱 (0) | 2022.01.18 |
| BOJ 1916 최소비용 구하기 (0) | 2022.01.12 |
