Codeforces Round #719 To Go Or Not To Go? - BFS

题意

给你一张$n\times m$的地图,从$(1,1)$出发,要走到$(n,m)$。每次向相邻格子走一步的开销是$w$。图上有传送门,从传送门传送的开销是$map[x_1][y_1]+map[x_2][y_2]$。问你最小开销是多少。

题解

这是一个最短路问题,但不要使用dijkstra或者SPFA。因为这样的时间复杂度大概是$O(nm\cdot log(nm))$,多一个$log$容易T。

直接从起点$(1,1)$BFS,得到不经过传送门,从起点出发到所有点的距离$dis1$。再从$(n,m)$BFS,得到不经过传送门,从终点出发到所有点的距离$dis2$。

于是我们就能扫一遍所有的传送门,分别得到从起点和终点出发,能到达的,预付了这一侧的传送开销的,最小开销的,传送门。分别记为:min_trans_from_start和min_trans_from_end。显然$min\_trans\_from\_start=min(map[i][j]+dis1[i][j]) $,$min\_trans\_from\_end=min(map[i][j]+dis2[i][j]) $。

于是最终结果就是$min(dis1[n][m], min\_trans\_from\_start + min\_trans\_from\_start)$

代码

Submission #115342366 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论