Bus Companies

题目描述

有 n 个城市和 m 家公交公司。每家公交公司在特定的城市运营并以特定的价格出售车票。从某家公交公司购买车票可以让你在该公司运营的任意两个城市之间旅行。\n确定从 Syrjälä 到每个城市的最便宜路线的费用。

输入格式

第一行有两个整数 n 和 m：城市数和公交公司数。城市编号为 1,2,\dots,n，且城市 1 为 Syrjälä。\n接下来一行有 m 个整数 $c_1, c_2,\dots, c_m$：每家公交公司的车票费用。\n之后，有 m 对行描述每家公交公司的城市。\n每对的第一行有一个整数 k：该公交公司运营的城市数。\n每对的第二行有 k 个互不相同的整数 $a_1, a_2,\dots, a_k$：该公交公司运营的城市。\n你可以假设可以从 Syrjälä 到达所有其他城市。

输出格式

输出 n 个整数：从 Syrjälä 到城市 1,2,\dots, n 的最便宜路线费用。

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

0 5 4 4 3

提示

$1 \le n, m \le 10^5$ $1 \le c \le 10^9$ $2 \le k \le n$ $1 \le a \le n$ $k$

标签: CSES3158|高级图论问题

来源

CSES3158|高级图论问题