板子题合集。
唯一的难点在于没告诉我们要考试 (悲)
但是 \(AK\) 力 (喜)
T1 交通管制
题面
最短路。
正解应该是记录路径,然后将路径上每一条边 \(\times \ 2\) 后跑最短路,统计答案,极限复杂度 \((O) \ nlog(n)m\)
但可以直接遍历所有的边,复杂度 \((O) \ n \ log(n) \ m\) (\(Dijkstra\)) 或 \((O)nm^2\) (\(SPFA\))
\((O) \ n \ log(n) \ m\) 显然可以过,而由于没有卡 \(SPFA\) 的原因 , \((O)nm^2\) 也可过(逃)
赛时打的 \(SPFA\) 过了