2417. [HZOI 2016]在路上

【题目描述】

小F想从宿舍去机房。但是在去机房的路上他还需要顺便拜访其他地点，比如去图书馆借书，比如去食堂吃饭。经过这些地点的顺序不是随意的，比如小F不希望在去教室放完东西之后才去图书馆借书(因为他要把借到的书放到教室)。由于小F的时间比较紧，他希望在满足以上限制的同时，所走过的路长度最短。

学校是一个有n个点m条边的无向连通图，地点自1至n依次编号，道路亦然。没有从某个地点直接到它自己的道路，两个地点之间最多只有一条道路直接相连。每条道路都有一个固定长度。在中途，小F想要经过k(k<=n-2)个地点。宿舍编号为1，机房编号为n,而小F想要经过的K个地点编号依次为2,3,…,k+1。

对于样例来说，小F想要经过地点2,3,4,5，并且在2停留的时候在3之前，而在4,5停留的时候在3之后。那么最短的走路方案是1-2-4-3-4-5-8，总长度为19。注意小F为了从地点2到地点4可以路过地点3,但不在地点3停留。这样就不违反小F的要求了。并且由于小F想要走最短的路径，因此这个方案正是小F需要的。

【输入格式】

第一行包含3个整数n(2<=n<=20000),m(1<=m<=200000),k(0<=k<=20),意义如上所述。以下m行，每行包含3个整数x，y，z，(1<=x，y<=n，0<z<=1000)；

接下来一行，包含一个整数q，表示有q个限制条件(0<=q<n)。以下q行，每行两个整数f，l(1<=l，f<=n)，表示在f停留的时候要在l之前。

【输出格式】

只包含一行，包含一个整数，表示最短的走路距离。

【样例输入】

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

【样例输出】

19

【提示】

没啥提示

【来源】

HZOI 2016