P1119 灾后重建¶

图论 #最短路¶

题目背景¶

B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

题目描述¶

给出 B 地区的村庄数 \(N\)，村庄编号从 \(0\) 到 \(N-1\)，和所有 \(M\) 条公路的长度，公路是双向的。并给出第 \(i\) 个村庄重建完成的时间 \(t_i\)，你可以认为是同时开始重建并在第 \(t_i\) 天重建完成，并且在当天即可通车。若 \(t_i\) 为 \(0\) 则说明地震未对此地区造成损坏，一开始就可以通车。之后有 \(Q\) 个询问 \((x,y,t)\)，对于每个询问你要回答在第 \(t\) 天，从村庄 \(x\) 到村庄 \(y\) 的最短路径长度为多少。如果无法找到从 \(x\) 村庄到 \(y\) 村庄的路径，经过若干个已重建完成的村庄，或者村庄 \(x\) 或村庄 \(y\) 在第 \(t\) 天仍未重建完成，则需要返回 -1。

输入格式¶

第一行包含两个正整数\(N,M\)，表示了村庄的数目与公路的数量。

第二行包含\(N\)个非负整数\(t_0, t_1,…, t_{N-1}\)，表示了每个村庄重建完成的时间，数据保证了\(t_0 ≤ t_1 ≤ … ≤ t_{N-1}\)。

接下来\(M\)行，每行\(3\)个非负整数\(i, j, w\)，\(w\)为不超过\(10000\)的正整数，表示了有一条连接村庄\(i\)与村庄\(j\)的道路，长度为\(w\)，保证\(i≠j\)，且对于任意一对村庄只会存在一条道路。

接下来一行也就是\(M+3\)行包含一个正整数\(Q\)，表示\(Q\)个询问。

接下来\(Q\)行，每行\(3\)个非负整数\(x, y, t\)，询问在第\(t\)天，从村庄\(x\)到村庄\(y\)的最短路径长度为多少，数据保证了\(t\)是不下降的。

输出格式¶

共\(Q\)行，对每一个询问\((x, y, t)\)输出对应的答案，即在第\(t\)天，从村庄\(x\)到村庄\(y\)的最短路径长度为多少。如果在第t天无法找到从\(x\)村庄到\(y\)村庄的路径，经过若干个已重建完成的村庄，或者村庄x或村庄\(y\)在第\(t\)天仍未修复完成，则输出\(-1\)。

样例 #1¶

样例输入 #1¶

样例输出 #1¶

-1
-1
5
4

提示¶

对于\(30\%\)的数据，有\(N≤50\)；

对于\(30\%\)的数据，有\(t_i= 0\)，其中有\(20\%\)的数据有\(t_i = 0\)且\(N>50\)；

对于\(50\%\)的数据，有\(Q≤100\)；

对于\(100\%\)的数据，有\(N≤200\)，\(M≤N \times (N-1)/2\)，\(Q≤50000\)，所有输入数据涉及整数均不超过\(100000\)。

Code¶

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <stack>

using namespace std;
typedef pair<int, int> PII;
typedef long long LL;

const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
const int K = 1e3 + 10;

int n, m;
int ti[N];

LL g[K][K];
int x, y, t;
int p;

int floyd()
{
    while (ti[p] <= t)
    {
        int k = p;
        p++;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (g[i][k] != INF && g[k][j] != INF)
                {
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
                }
            }
        }
    }
    if (ti[x] > t || ti[y] > t || g[x][y] >= INF)
    {
        return -1;
    }
    else
    {
        return g[x][y];
    }
}

int main()
{
    cin >> n >> m;
    memset(g, INF, sizeof(g));
    for (int i = 0; i < n; i++)
    {
        cin >> ti[i];
    }
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = g[b][a] = w;
    }
    int q;
    cin >> q;
    ti[n] = INF;
    for (int i = 0; i < q; i++)
    {
        cin >> x >> y >> t;
        cout << floyd() << endl;
    }

    return 0;
}