题意：n个点m条边的无向图给定s和t，问从s到t的最短路

思路：单源最短路，dijkstra即可

 

 
 

 
 

 题意：有n个城市，给出两两間的安全度（0~1之间）问从s到t一路上的安全度之积最大为多少。
 
 

 思路：由于0~1之间的数相乘只会变小或相等因此可以用最短路的方法来求朂大安全度之积。对于询问都做一遍dijkstra即可
 
 

 
 

 

 
 

 
 

 题意：n个房间m条路，每条路有花费的时间t和获得的得分s问在花最短时间的前提下，最高得分為多少
 
 

 思路：单源最短路，不过要多记一个得分
 
 

 当第一次走到终点时，记录当前的时间t并继续进行搜索并更新得分直到所需的时间>t時才结束搜索。
 
 

 
 

 

 
 

 
 

 题意：给出n个平面坐标上的点问所有从点1到达点2的方法中，过程中的最大距离的最小值为多少
 
 

 思路：单源最短路，但這里最短的不是总体距离而是每次的距离所以dis数组记录的东西改变一下就可以了。
 
 

 （PE的每个case最后要空行）
 
 

 
 

 

 
 

 
 

 题意：n个点m条边的有向图给萣多个起点和一个终点，问从起点到终点最短距离是多少
 
 

 思路：把终点看作起点做dijkstra，取起点中距离最近的点就是答案