PAST5I
https://gyazo.com/01513f650068f7946cc04b839444666a
Initial Considerations
You can only move from higher elevations to lower elevations.
directed graph
Lots of goals.
Bundling around cost 0?
Let's do the latter, and if not, let's do the former.
Consideration complete
mounting
If we were to do the Dijkstra method anyway, the additional man-hours to implement the former would not be significant, so we decided there was no advantage to doing the latter.
Additional code to implement the former : (1).
AC
code:python
def solve(N, M, K, HS, CS, ABS):
from collections import defaultdict
edges = defaultdict(dict)
for i in range(M):
frm -= 1
to -= 1
to, frm = frm, to
# reversed edge
goal = N
for c in CS:
distances = one_to_all(goal, N + 1, edges)
INF = 9223372036854775807
for i in range(N):
if d == INF:
d = -1
print(d)
---
This page is auto-translated from /nishio/PAST5I. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.