CF545E Paths and Trees（比官方数据范围小）

题目描述

小女孩 Susie 偶然发现了她哥哥的笔记本。她有很多事情要做，比解题更重要，但她发现这道题非常有趣，所以她想知道它的答案并决定向你请教。因此，题目的描述如下：

假设给定一个连通的带权无向图 $G=(V,E)$（其中 $V$ 是顶点集，$E$ 是边集）。从顶点 $u$ 出发的最短路树是指这样一个图 $G_{1}=(V,E_{1})$，其中 $E_{1}$ 是初始边集 $E$ 的子集，且 $G_1$ 是一棵树，并且从 $u$ 到任意顶点的最短路径在 $G$ 和 $G_1$ 中长度相同。

你被给定一个连通的带权无向图 $G$ 和顶点 $u$。你的任务是找到一棵以 $u$ 为根、边权和尽可能小的最短路树。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 7.5 \times10^{4}$，$0 \leq m \leq 1.5 \times10^{5}$），表示图中顶点和边的数量。

接下来的 $m$ 行，每行包含三个整数，表示一条边——$u_i, v_i, w_i$——分别为这条边连接的两个顶点以及这条边的权值（$u_i \neq v_i, 1 \leq w_i \leq 10^9$）。保证图是连通的，且任意一对顶点间最多只有一条边。

输入的最后一行包含一个整数 $u$（$1\leq u\leq n$），表示起始顶点的编号。

输出格式

第一行输出该树所有边的最小总权值。

第二行输出构成这棵树的各条边的编号，编号从输入顺序的 $1$ 开始，按任意顺序输出多个编号，每个编号之间用空格隔开。

如果存在多组答案，输出其中任意一组均可。

输入输出样例 #1

输入 #1

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

输出 #1

2
1 2 

输入输出样例 #2

输入 #2

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

输出 #2

4
2 3 4 

说明/提示

在第一个样例中，存在两种可能的最短路树：

• 选边 $1-3$ 和 $2-3$（总权值为 $3$）；
• 选边 $1-2$ 和 $2-3$（总权值为 $2$）；

例如，选边 $1-2$ 和 $1-3$ 的树并不是以 $3$ 为根的最短路树，因为此时从顶点 $3$ 到顶点 $2$ 的距离是 $3$，而在原图中的最短距离是 $1$。

由 ChatGPT 5 翻译