Skip to content

11394: 【原1394】小Q的难题

题目

题目描述

author: greatwall1995 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1394

Description

奢则不孙,俭则固。与其不孙也,宁固。

小Q是个热爱探索的女孩。今天,小Q又打算体验一下她所在的城市的公交系统。她对这次探寻过程做出了以下几个要求:

  • 起点和终点必须相同。
  • 不能两次乘坐同一条路线上的公交车。
  • 整个旅程的费用尽可能小。

现在,小Q已经弄清楚了每个公交线路途经的公交站点以及每个公交线路的票价。请你告诉小Q她最少需要花费多少钱才能完成这次旅行。

Input Format

第一行输入两个正整数n, m,分别表示公交车站的数量和公交线路的数量。

接下来m行每行描述一条公交线路的信息:首先读入两个整数t,c,分别表示这条公交线路途径公交站点的数量以及票价。紧接着读入t个整数,表示该公交线路途径的站点编号。(站点编号均为1到n之间的正整数。对于每条公交线路同一个站点不会重复出现。)

Output Format

输出一个正整数表示答案。

Sample Input

5 3
3 1 1 2 3
3 1 3 4 5
2 1 5 1

Sample Output

3

Limits

对于20%的数据,2≤n,m≤5

对于40%的数据,2≤n,m≤10

对于100%的数据,2≤n,m≤100

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!