题目描述

某会议有 $n$ 名参会者，编号为 $1$ 到 $n$。前 $m$ 名参会者（编号 $1$ 到 $m$）每人拥有一辆车，可以在活动结束后驾车回家。其余 $n - m$ 名没有车的参会者将借助前 $m$ 名参会者的帮助搭车回家。前 $m$ 名参会者每人最多可以搭载另一名参会者（从编号 $m+1$ 到 $n$ 的参会者中选择），并在返回自己家之前先将该人送回家。已知 $n+1$ 个地点（会议厅和 $n$ 名参会者的家）的距离矩阵 $D$。请为有车的参会者安排搭载无车参会者回家的方案，使得所有参会者到达各自家的时间最短。距离矩阵 $D$ 是一个 $(n+1) \times (n+1)$ 的矩阵，其中 $D[i][j]$ 表示从地点 $i$ 到地点 $j$ 的预估运输时间。地点 $i$（$1 \leq i \leq n$）表示第 $i$ 名参会者的家，会议厅位于地点 $n+1$。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 500$ 且 $1 \leq m \leq n$）。保证 $2m \geq n$。

接下来的 $n+1$ 行描述了距离矩阵 $D$，每行包含 $n+1$ 个整数。输入的第 $i+1$ 行（$1 \leq i, j \leq n+1$）的第 $j$ 个数指定了 $D[i][j]$（$0 \leq D[i][j] \leq 10^8$）。保证对于任意 $1 \leq i, j, k \leq n+1$，有 $D[i][k] \leq D[i][j] + D[j][k]$，且当 $i = j$ 时 $D[i][j] = 0$，但 $D[i][j]$ 不一定等于 $D[j][i]$。

输出格式

输出的第一行应打印所有参会者到达各自家的最短时间。接下来的 $m$ 行中，每行 $i$（$1 \leq i \leq m$）应包含一个非负整数 $t_i$，表示第 $i$ 名参会者的驾驶安排。如果 $t_i = 0$，则表示该参会者直接驾车回家，不搭载任何其他人。否则（$t_i > 0$），表示第 $i$ 名参会者搭载参会者 $t_i$，并在驾车回自己家之前先将该人送回家。每位无车参会者必须恰好由一辆车运送。

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

4
0
3

提示

翻译由 DeepSeek V3 完成