题目链接
题意：大概是说有几个村庄，村庄之间有几条马路，但是村庄被毁了需要重修，修不同的村庄需要不同的天数，只有当两个村庄都被修好时两个村庄之间的道路才能通行。现在给出询问天数，问你在第t天时a和b村庄是否有最短通路（前提是两个村庄都被修好了）。 代码如下：
#include <bits/stdc++.h> using namespace std; #define inf 1e9 int n, m, day[202], dp[202][202]; void updata(int now) { //这里其实就是Floyd算法的具体体现 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (dp[i][j] > dp[i][now] + dp[now][j]) dp[i][j] = dp[j][i] = dp[i][now] + dp[now][j]; } } } int main() { cin >> n >> m; for (int i = 0; i < n; ++i) cin >> day[i]; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) dp[i][j] = inf; for (int i = 0; i < n; ++i) dp[i][i] = 0; for (int i = 0, a, b, w; i < m; ++i) { cin >> a >> b >> w; dp[a][b] = dp[b][a] = w; } int num, now = 0; cin >> num; for (int i = 0, x, y, t; i < num; ++i) { cin >> x >> y >> t; while (day[now] <= t && now < n) { updata(now); now++; } if (day[x] > t || day[y] > t || dp[x][y] == inf) { cout << -1 << endl; } else cout << dp[x][y] << endl; } return 0; }题解：没什么特别的，要注意的是inf的初始化值，因为要尽可能设一个最大值，但是不能太大，因为在updata里面要执行dp[i][now] + dp[now][j]，所以这两个相加的结果最大不能超过int的最大值，不然会乱码（我就是一开始设了0x7fffffff，然后wa了）。
