https://www.acmicpc.net/problem/24042

공식풀이는 가중치가 동적으로 결정되는 다익스트라. 이것도 동적인 가중치라고 보는것보다 현재거리%m이 정점u이고 인접한 다음간선이 i일때 다익스트라하는 느낌으로 볼 수 있는듯 왜냐하면 간선정점 바뀌어있어도 타고온 간선이 어떤건지 정보가 거리정보를 통해 추론이 가능하기 때문.

내 풀이는 간선을 정점으로 보는 새로운 그래프에 간선을 주는데, 한 정점에 모이는 여러 간선은 쌍이 N^2이 되므로 TLE 피하기 위해 단조성 하나 더 활용해서 시간인접한것끼리에만 간선생성해주는 모델링으로 해결했다.

근데 어떻게 변형해야 내 풀이로만 푸는 문제가 되는지는 모르겠다. 애초에 논리상 동치인걸수도? 앳코더에 시간별로 뭔가 간선이 mod내에서 변화하는 문제가 있던거같은데 내 모델링과 비슷한거로 기억한다. [BOJ5214환승,2021최소환승경로]문제와 비슷하게 N^2회피해야 하는 문제인데, 환승은 방사형으로 모델링되고(n^2개의 모든 간선가중치가 동일) 횡단보도는 원형으로 모델링되었다(n^2개의 간선가중치들끼리 포함관계가 성립하는 구조. 어떠한 대수구조를 이룬다고 할 수 있을듯)

prim(mst)과 bottleneck문제가 다익스트라의 가중치변형으로 볼 수 있을까?
prim: d[y]=0*d[x]+w
bottleneck이 아니라 widest path인듯. boj에 중량제한인가 뭔가하는 문제였던듯: d[y]=max(d[x],w)
이게 그 매트로이드구조인가 뭔가하는거로 설명이 되는 느낌??? 아무튼 뭔가 추상적으로 통합해 표현되는 뭔가 있을거같다.

사실 이론상 복잡도는 정점을 [정점][들어온 간선]으로 정의하면 정점별 hashmap으로 동일하게 보장해줄 수 있는데 해시맵이라 ps에선 힘들듯. 이분탐색해서 log^2으로 풀리긴 하는듯.
정점을 [간선][간선양끝점 구분]으로 정의하면 E*2 상태로 문제를 풀 수 있음. 그러나 이경우 제한이 간선이 많아 TLE날듯함.
내 풀이는 이 정의에서 [간선 양끝점 구분]을 없애고 [간선]들 사이에 간선을 효율적으로 부여해주는 방법이다. 아슬아슬하게 통과함.
공식해설은 [정점][들어온간선]의 정의에서 [들어온 간선]을 distance[x]%m으로 추론가능하며 [정점]이 같은값이면 [들어온간선]이 다른것들중에서 제일 빨리도착한거가 지배한다는 추가적인 가정을 통해 다익스트라를 하게 되는것이라고 이해했다.