#P17012. [SGU503] Running City

[SGU503] Running City

[SGU503] Running City

题目描述

给定一张有向带权图。你需要从起点 SS 跑到终点 TT,第 ii 条边有基础耗时 cic_i。

除此之外,还有若干条“特殊路线”。每条特殊路线由一串边编号组成,并保证这些边构成一条不重复经过顶点的合法有向简单路径。

如果你的实际行走路径中,完整连续地经过了某条特殊路线,那么在走完这条特殊路线时会额外损失一段时间,额外耗时恰好等于该特殊路线所有边的基础耗时之和。换句话说,这一段相当于被计算了两次。

若路径中同时出现多条特殊路线,则每一次出现都要分别计算额外耗时。输入中甚至可以出现完全相同的特殊路线,此时它们的惩罚会叠加。

求从 SS 到 TT 的最小总耗时。

输入格式

第一行五个整数 n,m,r,S,Tn,m,r,S,T:

  • 2≤n≤10002\le n\le1000;
  • 0≤m≤100000\le m\le10000;
  • 0≤r≤10000\le r\le1000;
  • 1≤S,T≤n1\le S,T\le n 且 S≠TS\ne T。

接下来 mm 行,每行三个整数 a,b,ca,b,c,表示一条从 aa 指向 bb、耗时为 cc 的有向边,其中 1≤a,b≤n1\le a,b\le n、a≠ba\ne b、1≤c≤10001\le c\le1000。每个顶点的出度不超过 1010。边按输入顺序编号为 1∼m1\sim m。

接下来 rr 行描述特殊路线。每行先给出整数 kk,随后给出 kk 个边编号。每条路线都是合法简单路径。

额外保证:

  • 所有特殊路线长度之和不超过 2m2m;
  • 每条边至多出现在 1010 条特殊路线中。

输出格式

若无法从 SS 到达 TT,输出一行 -1。

否则输出一行一个整数,表示从 SS 到 TT 的最小总耗时。

样例 1

样例输入

3 3 1 1 3
1 2 2
2 3 1
1 3 2
1 3

样例输出

3