AcWing 4275. Dijkstra序列 Java版
原题链接
简单
作者:
辣条_9
,
2024-12-07 12:17:34
,
所有人可见
,
阅读 1
import java.util.*;
public class Main {
static int INF = 0x3f3f3f3f;// 无穷大
static int N = 1010, M = 10010;
static int n, m, k;
static int[][] g = new int[N][M];// 邻接矩阵,存储点之间的距离
static int[] d = new int[N];// 存储起点到各个点的最短距离
static boolean[] use;// 标记是否已经访问过
public static boolean dijkstra(int[] a) {
use = new boolean[N];
Arrays.fill(d, INF);
d[a[0]] = 0;// 起点为a[0],到自己的距离为0
for (int i = 0; i < n; i++) {
int t = a[i]; use[t] = true;
for (int j = 1; j <= n; j++) {
// 如果t点到j点的距离小于d[j],则说明t点不是最短路径
if (!use[j] && d[t] > d[j]) {
return false;
}
}
// 更新t点到其他点的距离
for (int j = 1; j <= n; j++) {
d[j] = Math.min(d[j], d[t] + g[t][j]);
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i <= 1000; i++) {
Arrays.fill(g[i], INF);
}
for (int i = 0; i < m; i++) {
int a, b, c;
a = sc.nextInt();
b = sc.nextInt();
c = sc.nextInt();
g[a][b] = c;
g[b][a] = c;
}
// 调用 sc.nextInt()之后添加一个额外的 sc.nextLine() 来消耗换行符。
k = sc.nextInt(); sc.nextLine();
while(k-->0){
String[] s = sc.nextLine().split(" ");
int[] a = new int[n + 10];
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(s[i]);
}
boolean result = dijkstra(a);
if (result) System.out.println("Yes");
else System.out.println("No");
}
}
}