bzoj 5047

bzoj 5047
bzoj九月月赛题。
动态边权的最短路问题。
枚举边权会死超时,可是细想,可以预处理的呀。
设cost[i]表示时间为i的时候最早到的时间,那么dist[now]时刻到的话,通过这条边,最早到的时间就是dist[now]+cost[now%c]-(now%c).
枚举时间,然后倒着取最小值就行了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Foreignbill