图论01.最短路专题_学习笔记+模板

图论01.最短路专题_学习笔记+模板 一、定义与性质 ● 需要的前导知识点

• 路径
• 最短路
• 有向图中的最短路、无向图中的最短路
• 单源最短路、每对结点之间的最短路

● 最短路的性质

对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。

对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。

对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过 n n n ，边数不会超过 n − 1 n-1 n−1 。

二、最短路算法与模板 1.Floyd–适用于无负环图的最短路算法

• 用于求解图中任意两点间的最短路径
• 时间复杂度 O ( N 3 ) O(N^3) O(N3)，空间复杂度 O ( N 3 ) O(N^3) O(N3)(一维不优化) / 0 ( N 2 ) 0(N^2) 0(N2) (一维优化后)；
• 容易实现，且适用于一切无负环且存在最短路的图，无论有向无向、边权正负。

● 算法的实现

我们定义一个数组 f[k][x][y] ，表示只允许经过结点 1 1 1 到 k k k ，结点 x x x 到结点 y y y 的最短路长度。

很显然， f[n][x][y] 就是结点 x x x 到结点 y y y 的最短路长度。

我们来考虑怎么求这个数组

f[0][x][y] ：边权，或者 0 0 0 ，或者 + ∞ +\infty +∞ （ f[0][x][x] 什么时候应该是 + ∞ +\infty +∞ ？）

f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])

上面两行都显然是对的，然而这个做法空间是 O ( N 3 ) O(N^3) O(N3) 。

但我们发现数组的第一维是没有用的，于是可以直接改成 f[x][y] = min(f[x][y], f[x][k]+f[k][y]) ，

for (k = 1; k  b;
    q.push(a);
    ans[a] = 100.0;

    while(!q.empty()){
        int now = q.front();
        for(int i = 0; i  ans[now] / fee[now][i]){
                ans[g[now][i]] = ans[now] / fee[now][i];
                q.push(g[now][i]);
            }
        }
        q.pop();
    }
    printf("%.8lf", ans[b]);
    return 0;
}

[USACO07OCT]Obstacle Course S

Problem Description

Consider an N x N (1