题意
给你一张$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
