小明作为一名刚学习信息学的蒟蒻(即魔芋[luffy注]),一开始便感受到了这个领域深深的恶意.他决定每天下午外出跑步,以达到放松心情的目的.
小明生活的城市被分为n个地区,每两个地区间都可能存在一条双向联通的道路.而这些道路总共有k条.作为一名蒟蒻,他有着严重的强迫症, 因此,若两个地区间有多条直接联通道路,他会毫不犹豫地选择最长的那一条.
小明选择了作为神犇的你,帮助他求出在将来x天,从a区域到b区域的最短路径.
第一行3个数字,分别是n,k,x.n表示小明所在城市中地区的个数,k表示地区间道路的总数,x表示小明查询的天数.
接下来k行,每行有3个数(可能为小数,不要说我没提醒你用某数据类型):c,d,e,表示从c到d直接联通的道路的长度为e
接下来x行,每行两个整数:a,b,表示小明今天查询的从a到b的最短路径(如果答案小数部分不为0，保留1位小数，否则输出整数).
输出共x行,表示当天小明查询的最短路径
5 7 3 1 2 6 2 3 10 3 4 5 4 5 4 5 1 2 2 5 8 1 4 7 1 4 1 3 3 5
6 11 9
对于25%,n<=5且点i仅与点i+1相连(i+1<n),点i与点1相连(i=n)
对于另外50%,n<=15,n^2>k>n
对于最后25%,n=20,k>n^2
我不会告诉你C202207jiangjinbei(蒋金贝)已经试过了
本题目版权归luffy所有