Skip to content

11374: 【原1374】旅行

题目

题目描述

author: wkn 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1374

Description

给定一张N个点,M条有向边的图,前K个点是中间节点。

再给出Q个询问,给定u,v,找出从u到v,至少经过一个中间节点(u,v本身算)长度最短的路径。

输出存在路径的询问数和所有路径的长度和。

Input Format

第一行:M,N,K,Q

接下来M行,每行u,v,d表示从u到v有长度为d的单向边。

接下来Q行, 每行u,v,询问u到v之间是否有符合条件的单向路径(可以经过一个点多次)

Output Format

第一行 输出存在路径的询问数

第二行 输出存在路径的询问对应的最短路径的长度和。

Input Sample

3 2 1 2
2 1 1
1 3 1
2 3
3 2

Output Sample

1
2

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!