题目解析
先输出 最短路的条数 和 最短路上能最多召集多少人
在输出最短路上最多能召集人数的路径的点
解题思路
基础dijstra的模板 只不过加了人数 条数 路径
在更新最短路的同时 人数 条数 路径都需要更新
还有 最短路相同时 条数需要更新 但路径更新需要看人数来更新
注： java选手可能要多交几发才能a
代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Main
{
static int inf = 0x3f3f3f3f;
static int N = 500;
// 存储 i 这个点上的志愿者
static int shu[] = new int[N + 10];
// 存储地图
static int map[][] = new int[N + 10][N + 10];
// 存储 S - i 的最短路径长度
static int d[] = new int[N + 10];
// 存储是否被用过
static boolean vis[] = new boolean[N + 10];
// 存储 S -> i 的最短路 的 条数
static int num[] = new int[N + 10];
// 存储 S -> i 的最短路 上的 最多召集人数
static int sum[] = new int[N + 10];
// 存储 是由 pre[i] -> i 的 也就是 i 这个点是从哪个点来的
static int pre[] = new int[N + 10];
static int S, D;
static void print(int u)
{
if (u == S)
{
out.print(u);
return;
}
print(pre[u]);
out.print(" " + u);
}
public static void main(String[] args) throws IOException
{
int n = ini();
int m = ini();
S = ini();
D = ini();
for (int i = 0; i < n; i++)
shu[i] = ini();
// 初始化地图
for (int i = 0; i < n; i++)
Arrays.fill(map[i], inf);
// 地图路径赋值
while (m-- > 0)
{
int u = ini();
int v = ini();
int w = ini();
map[u][v] = map[v][u] = Math.min(map[u][v], w);
}
// 初始化 S 到各点的距离
Arrays.fill(d, inf);
// S -> S 的距离为0
d[S] = 0;
// S -> S 只有一种路径选择
num[S] = 1;
// S -> S 最多召集的人数为 S这个点上的人数
sum[S] = shu[S];
for (int i = 0; i < n; i++)
{
// 寻找与起点最短距离的点
int t = -1;
for (int j = 0; j < n; j++)
{
if (!vis[j] && (t == -1 || d[t] > d[j]))
t = j;
}
// 标记该点的最短距离已经确定了 然后用确定的点更新其他点的最短距离
vis[t] = true;
// 用已经确定了的最短距离的点来更新到其他点的最短距离
for (int j = 0; j < n; j++)
{
// 如果 起点到j的距离 比 起点到t的距离加上t到j的距离 远时
// 那么就要更新所有值
if (d[j] > d[t] + map[t][j])
{
// 距离更新
d[j] = d[t] + map[t][j];
// 人数更新
sum[j] = sum[t] + shu[j];
// 条数更新
num[j] = num[t];
// 当前从哪个点来的更新
pre[j] = t;
}
// 如果 起点到j的距离 比 起点到t的距离加上t到j的距离 相等
else if (d[j] == d[t] + map[t][j])
{
// 如果 当前从起点到j召集的人数 比 起点到t点的召集的人数 多时
// 需要更新人数 和 当前从哪个点来
if (sum[j] < sum[t] + shu[j])
{
sum[j] = sum[t] + shu[j];
pre[j] = t;
}
// 条数增加
num[j] += num[t];
}
}
}
// 输出 条数 以及 人数
out.println(num[D] + " " + sum[D]);
// 递归打印路径
print(D);
out.flush();
out.close();
}
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(System.out);
static int ini() throws IOException
{
sc.nextToken();
return (int) sc.nval;
}
static String ins() throws IOException
{
sc.nextToken();
return sc.sval;
}
}