[일반] 앳코더 e번 어케품??

[익명(14.40)]

난 다익으로 풀려고 햤는데 정점에 적힌 숫자 크기가 같으면 무한루프 빠져서 이거 해결 못했어

[익명(210.179)]

저도 그것땜에 ㅇㅇ..

[익명(121.135)]

같은 정점을 scc로 묶어야됨

[익명(121.135)]

근데 다익하면 최'단'거리가 나오는데 이 문제는 dag에서 1 to n가는 최'장'거리 구하는거잖아 잘 생각해봐

[익명(14.40)]

내 말은 다익의 논리로 풀었다는거 암튼 ㄱㅅ

[익명(211.57)]

인접한 같은값 가진 정점 유파로 묶고 increasing sequence구하게하면 dag dp

[익명(121.135)]

캬

[익명(210.179)]

omg

[익명(114.206)]

아니 근데 이걸 왜 다익이나 bfs로 하면 터짐?

[익명(121.135)]

최단거리면 몰라도 최장거리를 다익이랑 bfs로 구하려는 시도잖음 왜 안될까 생각해보셈

[익명(114.206)]

거리를 음수값으로 했는데도 안 됨

[익명(114.206)]

AC 코드:
https://atcoder.jp/contests/abc335/submissions/49127206
TLE
코드:
https://atcoder.jp/contests/abc335/submissions/49127328
유일한
차이점은 cmp 함수의 정렬 기준임

[익명(114.206)]

pq에 대해서 정렬 기준을 배열 A가 더 작은 걸 거리 상관 없이 먼저 오게 해야하는 게 직관적으로 이해가 안됨.

[익명(114.206)]

https://atcoder.jp/contests/abc335/submissions/49122591
거리
음수로 계산한 TLE 코드