https://www.acmicpc.net/problem/9633
N<=150, M<=3000, Q<=1000
노드, 간선,쿼리
x->y : 가중치 z
입력 들어오고
Q마다 a,b,c 입력 들어오는데 a에서 b가는 increasing shortest path를 구하는데
이때 간선을 최대 c개만 써야한다.
increasing shortest path는 u->v->w라고 할때 v->w의 코스트가 u->v 코스트 보다 항상 커야함
즉 경로를 이루는 간선들이 a->b로 가면서 가중치가 단조증가하면서 최단거리를 이뤄야 하는데 이때 간선의 개수도 c개 이하여야함
매 쿼리마다 dijkstra돌리니까 시간이 터지네...
킹갓고수님들 이런거 어케풀어야함???
안풀어봐서 모르겠는데 가중치가 strict하게 증가해야 하면 그래프를 dag로 바꿔줄수 있고 그러면 문제가 높은 확률로 dp로 바뀜
그래프를 어떤식으로 DAG로 바꿔야 할까? 비슷한 기법 쓰는 문제좀 알려주십셔
14699?
ㄳㄳ 이런거 대회 시간내에 푸는 넘들은 정체가 뭘까
매 쿼리마다 dijkstra를 돌리지 말고 N번만 돌려놓으면 되는거아님?
N번 돌려서 모든쌍의 increasing shortest path를 구해놓고 쿼리마다 처리한다?
그게 맞는거같은데
ㄳㄳ