单源最短路算法, 不仅能用来求最短路, 还能用来求其他单源最值问题

最大值的思想和最小值的思想是一样的

路径边权和最小值

1.无负权边：dijkstra
2.有负权边：spfa

memset(dis, 0x3f, sizeof dis);
dis[st] = 0;
if(dis[j] > dis[t] + w[i])
    dis[j] = dis[t] + w[i];

路径边权和最大值

还未遇到, 待更新…

1. 乘积最值问题是可以转化为加法最值问题的(见acwing最小花费打卡的推导)
2. 乘积最值问题的边权必然都为正

路径边权乘积最小值

1.边权值的范围约束>=1：dijkstra
2.边权值的范围约束>0：spfa

memset(dis, 0x3f, sizeof dis);
dis[st] = 1;
if(dis[j] > dis[t] * w[i])
    dis[j] = dis[t] * w[i];

acwing最小花费 -> 单源定为B

路径边权乘积最大值

1.边权值的范围约束0-1：dijkstra
2.边权值的范围约束>0:spfa
-> 转化为加法之后>1的部分就会出现负权边(边权有的正有的负), 所以我们不能用dijkstra

memset(dis, 0, sizeof dis);
dis[st] = 1;
if(dis[j] < dis[t] * w[i])
    dis[j] = dis[t] * w[i];

acwing最小花费 -> 单源定为A