• 算法介绍

弗洛伊德算法是运用动态规划思想解决多源最短路的一种算法，
可以正确处理有向图或负权（但不可存在负权回路 这家伙无法判断负权)的最短路径问题，同时也被用于计算有向图的传递闭包。 
代码看起来很简短，但为啥说他是个动态规划呢？
因为这其实是一个三维动归问题，
令d[i][j][k]为只允许经过结点[0, k]的情况下，i 到 j的最短路。那么利用最优子结构性质，有两种情况：
      a. 如果最短路经过k点，则d[i][j][k] = d[i][k][k-1] + d[k][j][k-1];
      b. 如果最短路不经过k点，则d[i][j][k] = d[i][j][k-1];
于是有状态转移方程： d[i][j][k] = min{ d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1] }  (0 <= i, j, k < n)
这是一个3D/0D问题，只需要按照k递增的顺序进行枚举，就能在O(n^3)的时间内求解，第三维的状态采用滚动数组进行优化，所以空间复杂度为O(n^2)。
我们平时使用的floyd即为滚动数组优化的结果。
同时就有一个重要结论：i和j之间的最短路径上的结点集里(不包含i,j),编号最大的一个是x.那么在外循环k=x时,d[i][j]肯定得到了最小值.
证明借一下菊苣证明QWQ

  • 一（些？）题

题目链接：https://www.luogu.org/problem/P1119
因为每次的时间都是递增的，floyd中我们每次是拿k点去更新i，j。那么在判断的时候对k加一层判断即可。 
#include <bits/stdc++.h>
using namespace std;
#define INF  0x3f3f3f3f
#define s1(a) scanf("%d",&a)
#define stop system("pause")
#define lowbit(x)  ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)

int t[222];
int dp[222][222];
int main()
{
    
    int n,m;s2(n,m);
    mem(dp,INF);mem(t,INF);
    for(int i=0;i<n;i++) s1(t[i]),dp[i][i]=0;
    for(int i=0,u,v,c;i<m;i++)
        s3(u,v,c),dp[u][v]=dp[v][u]=c;
    int q,k=0;s1(q);
    while(q--)
    {
        int x,y,c;s3(x,y,c);
        for(;t[k]<=c;k++)
        {
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
        }
        if(t[x]>c||t[y]>c||dp[x][y]==INF) printf("-1\n");
        else printf("%d\n",dp[x][y]);
    }
    return 0;
}

  • [NOI2007]社交网络

https://www.lydsy.com/JudgeOnline/problem.php?id=1491
https://blog.csdn.net/KIKO_caoyue/article/details/91559961
我懒了。