单源最短路和最长路总结

单源最短路和最长路一共可分为：
$(1)$ 加法最短路
$(2)$ 加法最长路
$(3)$ 乘法最短路
$(4)$ 乘法最长路

下面就一一来分析一下~

1、 加法最短路

最基础的情况，用经典的单源最短路算法都可以求解。

2、 加法最长

可以用spfa；
当满足图中边权全为负数时，可以用dij。

3、 乘法最短路

可以用spfa；
当所有边权均满足w[i] >= 1时，可以用dij。

4、乘法最长路

可以用spfa；
当所有边权均满足0 < w[i] < 1时，可以用dij。

小结：关于dij在加法中，经典dij可在全负权边图中跑最长路、全正权边图中跑最短路。

分析方式总结

  套用最短路和最长路原理来分析，SPFA的正确性是基于它的松弛操作，所以自然是可以求乘积最小值和乘积最大值的。
  考虑Dij为什么不一定行，因为Dij的最短路算法是贪心的，它贪心的选最小的并且认为这个点不会被更新了，为什么不会被更新了？因为没有负权边，从而你加入优先队列里的dis只会越来越大，毕竟一个数+一个正数一定变大，不可能以后取出来某一个点更新这个点，故我这个点取出来了，就不会再使用。Dij的正确性是基于 “放入优先队列的点的dis是单调的” 这一条件。所以对于求最短路，我们要求dis单调递增，即不存在负权边，对于最大乘积，我们要求乘积只允许单调变小，即乘的在(0,1)之间，对于最小乘积，我们要求乘积必须单调变大，即所有边权都是>=1的。（似乎也不用严格单调，只要不增不减就行了）。

另外注意如果用Dij求最长路(加法/乘法)，那么记得要用大根堆。

例题

最小花费

朴素Dij做法

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 2010;
int n, m;
double w[N][N];
double dist[N];   //0表示不相连 
int S, T;
bool st[N];

void dijkstra(){
    dist[S] = 1;   //乘法的零元是1
    for(int i = 1; i < n; i++){
        int t = -1;
        for(int j = 1; j <= n; j++){
            if(!st[j] && (t == -1 || dist[j] > dist[t]))
                 t = j;
        }
        st[t] = true;
        for(int k = 1; k <= n; k++)
            if(dist[k] < dist[t] * w[t][k])
                dist[k] = dist[t] * w[t][k];
    }
}

int main(){
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; i++){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        w[x][y] = w[y][x] = (100 - z) / 100.0;
    }
    scanf("%d%d", &S, &T);

    dijkstra();
    printf("%.8f\n", 100 / dist[T]);

    return 0;
} 

堆优化版本dij

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef pair<double, int> PDI;
const int N = 2010, M = 200010;
int h[N], e[M], ne[M], idx;
double w[M], dist[N];
bool st[N];
int n, m;
int start, ed;

void add(int a, int b, double c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra(){
    priority_queue<PDI, vector<PDI>> heap;  //大根堆
    dist[start] = 1;
    heap.push({1, start});  //乘法的零元是1
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.y;
        double dis = t.x;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] < dis * w[i]){
                dist[j] = dis * w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

void solve(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while(m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, (100 - c) / 100.0), add(b, a, (100 - c) / 100.0);
    }
    scanf("%d%d", &start, &ed);
    dijkstra();
    printf("%.8lf\n", 100.0 / dist[ed]);
}

int main(){
    int T = 1;
    // scanf("%d", &T);
    while(T -- ){
        solve();
    }

    return 0;
}

spfa做法

#include <bits/stdc++.h>
using namespace std;

const int N = 2010, M = 200010;
int h[N], e[M], ne[M], idx;
double w[M];
double dist[N];
bool st[N];
int q[N], hh, tt;
int n, m, start, ed;

void add(int a, int b, double c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa(){
    dist[start] = 1;  //乘法的零元是1
    st[start] = true;
    hh = 0, tt = 0;
    q[tt++] = start;
    while(hh != tt){
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] < dist[t] * w[i]){
                dist[j] = dist[t] * w[i];
                if(!st[j]){
                    st[j] = true;
                    q[tt++] = j;
                    if(tt == N) tt = 0;
                }
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, 1.0 - 1.0 * c / 100);
        add(b, a, 1.0 - 1.0 * c / 100);
    }
    scanf("%d%d", &start, &ed);
    spfa();
    printf("%.8lf\n", 100.0 / dist[ed]);

    return 0;
}