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

Solution:

This is a shortest paths problem. But do not use Dijkstra or SPFA to solve this problem. Because the time complex is $O(nm\cdot log(nm))$. Can get TLE with an extra $log$.

Do BFS from the start point $(1,1)$. We get the shortest path from start point to all other points without pass through portal. Denoted as $dis1$.
Also do BFS from the end point $(n,m)$. We get the shortest path from end point to all other points without pass through portal. Denoted as $dis2$.

After that, we check all portals. We can get the portal that reachable, and paid cost of portal for current side, and the cost is the lowest from start point or end point. Denoted as $min\_trans\_from\_start$ and $min\_trans\_from\_end$ respectively. Obviously, $$min\_trans\_from\_start=min(map[i][j]+dis1[i][j]) $$ $$min\_trans\_from\_end=min(map[i][j]+dis2[i][j]) $$

So, the result is: $$min(dis1[n][m], min\_trans\_from\_start + min\_trans\_from\_start)$$

Code:

Submission #115342366 - Codeforces
Codeforces. Programming competitions and contests, programming community
DigitalOcean Referral Badge 蜀ICP备19018968号