问题 F: 人民公园

---

【题目描述】

【题目描述】
小智喜欢观景，于是今天他来到了人民公园。
已知公园有 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，其含义如题所述。
注意：输入的边可能有重复
1≤N≤400,1≤M≤ Nx(N-1)/2, Q≤1000,1≤u,v,st,ed≤n,1≤w≤1000000000
【输出描述】
输出共Q行，对应输入数据中的查询。
若无法从 st到达ed则输出-1。
【输入样例】
3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3
【输出】
1
3
2
 

【输入】

输入第一行包含三个正整数N,M,Q
第2到M+1行每行包含三个正整数u,v,w，表示u ↔v之间存在一条距离为w 的路。
第M+2到M+Q-1行每行包含两个正整数st,ed，其含义如题所述。
1≤N≤400,1≤M≤ Nx(N-1)/2, Q≤1000,1≤u,v,st,ed≤n,1≤w≤1000000000

【输出】

输出共Q行，对应输入数据中的查询。
若无法从 st到达ed则输出-1。

题目类型~

最短路 

咻咻~

提交答案 状态 返回作业