%%% srO 厉害的 朱$K$建 && 李佬 && 下铺王佬 Orz %%%
军训终于下了一次雨…于是来基房(大雾)水题….据说他们今天消防演习?

懵逼的 题目

传送至 Luogu

大意: 给定一个无向图 一开始图中没有点 然后不断向图中添点(和与她相连的边) 在这中间询问两点间的最短路

扯淡的 题解

因为提问数量太多 所以就想到Floyd处理每两点间的最短路 一想到Floyd 欸这不正好能做到添点嘛…于是…算法就呼之欲出了!QAQ
此题主要考察对Floyd的理解(即为什么k要放在最外边)

沙茶的 代码

//https://www.luogu.org/problem/show?pid=1119#sub
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define MAXN (200 + 5)
#define MAXQ (50000 + 5)
#define INF (0x7ffffff)
using namespace std;
struct que
{
    int from;
    int to;
    int time;
} q[MAXQ];
int n;
int m;
int t[MAXN];
int g[MAXN][MAXN];
int f[MAXN][MAXN];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &t[i]);
    }
    t[n] = INF;
    int srx, sry, srz;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            g[i][j] = f[i][j] = INF;
        }
        g[i][i] = f[i][i] = 0;
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &srx, &sry, &srz);
        f[srx][sry] = f[sry][srx] = g[srx][sry] = g[sry][srx] = srz;
    }
    int aq;
    scanf("%d", &aq);
    for (int i = 1; i <= aq; i++)
    {
        scanf("%d%d%d", &q[i].from, &q[i].to, &q[i].time);
    }
    int dq = 1;
    for (int k = 0; k < n; k++)
    {
        while (q[dq].time < t[k])// 这个地方保证中转点在时间范围之内
        {
            if (dq > aq)
            {
                return 0;
            }
            if (f[q[dq].from][q[dq].to] != INF && q[dq].time >= t[q[dq].to] && q[dq].time >= t[q[dq].from])// 这个地方保证开始和结束的两点在时间范围之内
            {
                printf("%d\n", f[q[dq].from][q[dq].to]);
            }
            else
            {
                puts("-1");
            }
            ++dq;
        }
        for (int i = 0; i < n; i++)// 注意:因为Floyd是dp 所以这个地方是一定要循环到(n - 1)的(否则下一次转移会GG) 所以判断是否符合时间范围的工作就放在了上面
        {
            for (int j = 0; j < n; j++)
            {
                if (f[i][k] != INF && f[k][j] != INF && (f[i][k] + f[k][j] < f[i][j]))
                {
                    f[i][j] = f[i][k] + f[k][j];
                }
            }
        }
    }    
    for (int i = dq; i <= aq; i++)
    {
        printf("%d\n", f[q[i].from][q[i].to]);
    }
}
/*
4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4
*/

By 逃(chen)了(mi)军(shui)训(ti)好开心的 Cansult