社区讨论

求助，是否存在原题

xx2401002
学术版参与者 6已保存回复 6

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mkjrv1d7
此快照首次捕获于
2026/01/18 21:28
上个月
此快照最后确认于
2026/01/22 18:05
4 周前
查看原帖

T713250 图论问题

题目描述

给定一个有nn个节点,mm条边的有向图，每个点有点权aia_i，每条边有边权viv_i。
现在有qq次询问,每次询问sis_i到tit_i的最短路,且经过的所有点点权小于kik_i,如果到达不了,输出−1-1。

输入格式

第11行，33个正整数n,m,qn,m,q
第22行，nn个正整数,表示每个点的点权。
第33行到第3+m3 + m行,每行33个正整数si,ti,vis_i,t_i,v_i
接下来qq行,每行33个正整数si,ti,kis_i,t_i,k_i,表示一次询问。

输出格式

一共qq行，表示每次询问的答案。

输入输出样例 #1

输入 #1

CPP
4 6 4
1 3 8 5
1 3 4
1 2 6
2 3 7
3 4 5
2 4 1
1 4 8
2 4 5
1 4 5
1 3 7

输出 #1

CPP
1
-1
4

说明/提示

对于3030%的数据保证,1≤n,q≤10,1≤m≤1021 \le n,q \le 10,1 \le m \le 10^2
对于另外的3030%的数据保证,1≤n≤102,1≤m≤103,1≤q≤1041 \le n \le 10^2,1 \le m \le 10^3,1 \le q \le 10^4
对于100100%的数据保证,1≤n≤5∗102,1≤m≤103,1≤q≤106,1≤vi,ki≤1091 \le n \le 5 * 10^2,1 \le m \le 10^3,1 \le q \le 10^6,1 \le v_i,k_i \le 10^9

注意空间100100MB

用原题机搜过了，但是要在学校出比赛，怕还有重题，求各位dalao判断一下

回复

共 6 条回复，欢迎继续交流。

正在加载回复...