蓝桥公园（蓝桥杯）

题目描述

小明喜欢观景，于是今天他来到了蓝桥公园。

已知公园有 N 个景点，景点和景点之间一共有 M 条道路。小明有 Q 个观景计划，每个计划包含一个起点 st 和一个终点 ed，表示他想从 st 去到 ed。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？

输入描述

输入第一行包含三个正整数N,M,Q

第 2 到M+1 行每行包含三个正整数 u,v,w，表示 u↔v 之间存在一条距离为 w 的路。

第 M+2 到 M+Q−1 行每行包含两个正整数 st,ed，其含义如题所述。

1leq Nleq 4001≤N≤400，1leq M leq dfrac{Ntimes(N - 1)}{2}1≤M≤2N×(N−1)​，Qleq 10^3Q≤103，1leq u,v,st,ed leq n1≤u,v,st,ed≤n，1leq w leq 10^91≤w≤109

输出描述

输出共 Q 行，对应输入数据中的查询。

若无法从 st 到达 ed 则输出 −1。

输入输出样例

示例 1

输入

 

3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3

输出

1
3
2

 第一次写如下，直接用floyd算法。结果是对的，但提交时结果超时了

import java.util.*;
public class Main{
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int nc=in.nextInt();//输入城市数目numbercity为nc
		int nr=in.nextInt();//道路数目numberrodad为nr
		int np=in.nextInt();//计划数目numberplan为np
		int [][]edge=new int[nr][3];//存储城市之间的通路和距离
		for(int i=0;i 
第二次写如下：还是超时了。或许这题要用c++，Java天生慢，这题无法pass
 
import java.util.*;
public class Main{
	static int m,n,q;
	static Scanner in=new Scanner(System.in);
	static int [][]dist=new int[401][401];
	
	
	public static void input() {
		int max=100000;
		for(int i=1;i<=n;i++)
			Arrays.fill(dist[i], max);
		for(int i=0;i