从标准输入读入数据。 输入的第一行包含三个由空格隔开的正整数 n,m,q,保证 N≤2,000 和 M≤8,000,Q≤10^5。 接下来的一行包括 n 个由空格隔开的非负整数 vi 表示编号从小到大所有点的价值,保证 vi≤10^4。 接下来的 m 行每行包含三个由空格隔开的正整数 x,y,z,保证 1≤x,y≤n 和 1≤z≤30,表示存在一条从 x 到 y 代价为 z 的有向边。 接下来的 q 行每行包含两个由空格隔开的非负整数 u,c,保证 1≤u≤n 和 0≤c≤800。
请先登录再刷题,不会做的题目右上可以查看题解和答案~
从标准输入读入数据。 输入的第一行包含三个由空格隔开的正整数 n,m,q,保证 N≤2,000 和 M≤8,000,Q≤10^5。 接下来的一行包括 n 个由空格隔开的非负整数 vi 表示编号从小到大所有点的价值,保证 vi≤10^4。 接下来的 m 行每行包含三个由空格隔开的正整数 x,y,z,保证 1≤x,y≤n 和 1≤z≤30,表示存在一条从 x 到 y 代价为 z 的有向边。 接下来的 q 行每行包含两个由空格隔开的非负整数 u,c,保证 1≤u≤n 和 0≤c≤800。
输出到标准输出。 对于每次询问输出一个数,表示相应的答案。
4 4 2 3 2 3 4 1 2 1 2 3 1 3 2 2 3 4 1 2 6 3 2
14 7
对于第一个询问最优方案是从 2 出发,经过 3,2,3,4 四个点,取得的价值是 2+3+2+3+4=14。 对于第二个询问最优方案是从 3 出发,经过 4 这个点,取得的价值是 3+4=7。
清华大学2020年机试题