列表

详情

NC224751. 逛漫展

描述

xmy来到黑职后和cr决定去逛漫展。
xmy这里有一份漫展的详细地图。
上面有N个展览场所，M条连接场馆的人行道。
xmy想要个程序处理这些数据，方便他和cr知道t时间从A场馆到B场馆的最短路程。
保证：每次查询的时间t，不小于上次查询的。
因为这个东西太简单了，所以让你去写一下练手。
以下为地图上的已知信息：
每个场所都标注了一个编号和开馆时间，的范围是0到N-1。并且编号小的场馆，开馆时间不会晚于编号大的,也就是说开馆时间是的

没有开馆的场馆是封锁的，不可以进入也不可以经过。
A与B之间的最短路径，是可以通过已经开馆的场馆进行中转来缩短的。

注：不要想太多，最短路程只计算场馆之间人行道的长度，不需要考虑利用场馆中转时需要在场馆内走的。

注：开馆后不会关馆。


输入描述

第一行三个整数 N M Q （N个场馆 M条人行道 Q次查询）
第二行N个整数，为开馆时间，以及据上文，给出的数据
 
以下M行 每行三个整数 A B W （表示场馆A与场馆B之间存在一条长度W的人行道）
       
以下Q行 每行三个整数 A B T     (表示要查询场馆A与场馆B之间在时间T的最短路径长度)
       

输出描述

共Q行，对每一个询问输出对应的答案
如果T时间 A，B未互通则输出-1

示例1

输入: 

4 4 4 
1 2 3 4
1 2 1
3 1 1
2 3 2
0 1 4
2 1 2
3 1 2
1 2 3
0 3 4

输出: 

-1
-1
1
5

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 191ms, 内存消耗: 1496K, 提交时间: 2022-10-19 22:46:27 

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

int n, m, q;
int T[205], dis[205][205];

void Floyd(int k) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
		}
	}
} 

int main() {
	cin >> n >> m >> q;
	for (int i = 0; i < n; i++) {
		cin >> T[i];
	}
	
	memset(dis, inf, sizeof dis);
	
	int a, b, w;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> w;
		dis[a][b] = dis[b][a] = min(w, dis[a][b]);
	}
	for (int i = 0; i < n; i++) {
		dis[i][i] = 0;
	}
	
	int k = 0;
	while (q--) {
		cin >> a >> b >> w;
		while (T[k] <= w && k < n) {
			Floyd(k++);
		}
		
		if (T[a] > w || T[b] > w) {
			puts("-1");
		}
		else {
			if (dis[a][b] == inf) puts("-1");
			else cout << dis[a][b] << '\n';
		}
	}
	return 0;
}

上一题

© 2024 nowcoder.com