- 此题的无穷大不能按题目给的不超过10000,不然会WA五个测试点,所以inf可以赋值为0x3f3f3f3f或者100000,即可通过;
- 而且每次询问的时候,可以发现每个村庄的修建时间是递增的,所以我们可以每次加一个可用村庄,也就是多一个中转点的选择,去更新整个邻接矩阵;
- 这个题目更深一层地了解Floyd算法,参考洛谷的题解:
#include
using namespace std;
int n, m;
int t[210];//每个村建设所需时间
int d[210][210];//邻接矩阵
int inf = 0x3f3f3f3f;
void floyd(int k) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
void init() {
//每个村庄维修所要的时间
for (int i = 0; i < n; i++)
cin >> t[i];
//初始化邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
d[i][j] = 0;
else
d[i][j] = inf;
}
}
for (int i = 0; i < m; i++) {
int x, y, val;
cin >> x >> y >> val;
d[x][y] = d[y][x] = val; //此题为无向图
}
}
int main() {
cin >> n >> m;
init();
int q;
int now = 0;//当前几个村已建成
cin >> q;
while (q--) {
int x, y, temp;
cin >> x >> y >> temp;
while (t[now] <= temp && now < n) {
floyd(now);///依次更新中转点,使它可以被用来更新其他的点
now++;
}
//某个村还未建成,不能省略这个条件判断,不然邻接矩阵有的值不为inf,会误以为可以到达,但这个村还没建成
if (t[x] > temp || t[y] > temp)
cout << -1 << endl;
else {
if (d[x][y] == inf)
cout << -1 << endl;
else
cout << d[x][y] << endl;
}
}
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)