#1687. >.<

    ID: 1687 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1037来源:qoj.ac数据:公开样例最短路径

>.<

>.<

题目描述

标题: >.< - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

Note. 「k 条路径」不一定在图中。

题目描述

有一张 n 个点,m 条边的带权有向图(无重边、自环),再给定 k 条路径,求一条 1 到 n 的最短路径(不要求是简单路径),使得这条路径不包含给定 k 条路径中的任何一条(包含指连续地经过某条路径)。输出此路径的长度,如果找不到输出 −1。

输入格式

第一行输入三个整数 n,m,k,表示图的点数、边数和钦定路径条数。 接下来 m 行,每行三个整数 ui,vi,wi 表示有一条从 ui 到 vi,边权为 wi 的有向边。 接下来 k 行,每行先输入一个整数 p,表示这条给定路径的长度,后面有 p 个整数,描述了这条给定的路径。

输出格式

输出一行一个整数表示从 1 到 n 不经过给定路径的最短长度。如果不存在输出 −1。

样例一

input

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

output

8

样例二

input

4 4 2
1 2 1
2 3 1
3 4 1
3 2 1
4 1 2 3 4
6 1 2 3 2 3 4

output

7

子任务

以下的路径长度均指一条路径经过的点个数(重复点算多次)。

  • Subtask1(20 pts):n,m≤100,k=0;
  • Subtask2(20 pts):n,m≤100,每条给定路径长度不超过 4;
  • Subtask3(30 pts):n,m≤2×105,k=1;
  • Subtask4(30 pts):n,m,k≤2×105。

对于所有数据,有 1≤n,m≤2×105,0≤k≤2×105,1≤ui,vi≤n,0≤wi≤109,路径长度总和小于等于 2×105。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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

样例 2

4 4 2
1 2 1
2 3 1
3 4 1
3 2 1
4 1 2 3 4
6 1 2 3 2 3 4
7