풀이
문제를 다르게 생각해보자.
마지막에 도착하는 사람까지 도착을 하는 시간 이라는 문장은 결국 가장 먼 길을 선택하는 사람, 즉 최장 거리를 의미한다.
따라서 이 문제는 최장 거리와, 최장 경로들에 포함되는 모든 간선의 개수를 카운팅해서 출력하면 된다!
풀다보니까 이게 개수를 카운팅 할 때 뒤에서 부터 돌아야 할 것 같은데… 인접행렬이 아니라 백터를 써서 짰단 말이야
코드를 다시 짜긴 귀찮고 그래서 dp 배열을 아예 백트랙킹? 그런 느낌으로 구했다.
get_max_len() 함수를 보면 일단 카운팅하기 전에 끝까지 다 들어가놓고, 다시 나오면서 dp[now] = max() 하는 걸 볼 수 있다.
근데 왜 배열 이름을 dp로 했더라
코드
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct ABC {
int idx, val;
ABC() {}
ABC(int idx, int val) : idx(idx), val(val) {}
};
int n, m, s, e, ans, dp[10001];
bool chk[10001];
vector<ABC> A[10001];
void get_max_len(int now) {
for (auto nxt : A[now]) {
int nn = nxt.idx, nw = nxt.val;
if (!dp[nn]) get_max_len(nn);
dp[now] = max(dp[now], dp[nn] + nw);
}
}
void get_max_cnt(int now) {
if (chk[now]) return;
chk[now] = true;
for (auto nxt : A[now])
if (dp[nxt.idx] + nxt.val == dp[now])
++ans, get_max_cnt(nxt.idx);
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < m; ++i) {
int a, b, w;
scanf("%d %d %d", &a, &b, &w);
A[a].push_back(ABC(b, w));
}
scanf("%d %d", &s, &e);
get_max_len(s);
get_max_cnt(s);
printf("%d\n%d", dp[s], ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이