TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3761
  • 题目
  • P3761送外卖
    限制 : 时间限制 : - MS   空间限制 : 365536 KB
    评测说明 : 时限1000ms
    问题描述

      暑期期间,何老板闲来无事,于是买了辆摩托车,签约某团外卖,跑起来送外卖的业务。
      何老板负责的区域里有n个住宅小区(编号1到n),小区间通过m条双向道路相连,两个小区间最多只有一条道路相连,也不存在某小区自己到它自己的道路。每条道路有一定的长度。
      何老板先到1号小区的餐馆去领餐,然后去k个小区送餐(编号2,3,4,...,k+1),最终到n号小区的加油站去给摩托车加油。要到k个小区去送餐,根据下单时间,公司规定了其中某些小区送餐的先后顺序,比如i小区的餐必须在给j小区送餐前送到。何老板希望在满足公司要求的情况下,使得行走的总路程最少,请你帮他计算一下。
      例如,下图所示,起点为1号终点为8号小区。期间要给2、3、4、5号小区送餐。公司规定,给2号小区送餐后才能给3号小区送餐,给3号小区送餐后才能给4、5号小区送餐。最短的行程方案是1—>2—>4—>3—>4—>5—>8,总路程为19。


       注意,可以先经过某些后送餐的小区而不停下来给它们送餐。假如,要送4号小区后才能给3号小区送餐,何老板可以从2号经过3号到达4号小区,中间虽然经过了3号小区,但他没有停下来,这样就不违法公司的规定了。

    输入格式

    第一行,3个空格间隔的整数n,m,k

       接下来m行,每行三个整数x,y,z表示小区x也小区y间有一条长度为z的道路(1<=x,y<=n   1<=z<=1000)

       接下来一行,一个整数t,表示公司有t条要求(0<=t<=k*(k-1)/2)

       接下来t行,每行两个整数x和y,表示给x小区送餐后才能给y号小区送餐
       (2<=x,y<=k+1   x!=y)

    输出格式

    一行,一个整数,表示所求最短总路程。

    样例输入 1

    8 15 4
    1 2 3
    1 3 4
    1 4 4
    1 6 2
    1 7 3
    2 3 6
    2 4 2
    2 5 2
    3 4 3
    3 6 3
    3 8 6
    4 5 2
    4 8 6
    5 7 4
    5 8 6
    3
    2 3
    3 4
    3 5

    样例输出 1

    19

    样例输入 2

    8 7 6
    1 2 10
    2 3 15
    3 4 1
    4 5 12
    5 6 13
    6 7 123
    7 8 10
    5
    7 2
    2 6
    6 3
    3 5
    5 4

    样例输出 2

    588

    提示

    对于100%的数据 2<=N<=20000, 1<=M<=200000, 0<=K<=20


    来源  改编自POI2007 atr