【ACWing】4275. Dijkstra序列

题目地址：

https://www.acwing.com/problem/content/description/4278/

Dijkstra算法是非常著名的贪心算法之一。它用于解决单源最短路径问题，即指定一个特定源顶点，求该顶点到给定图的所有其他顶点的最短路径。它由计算机科学家Edsger W. Dijkstra于$1956$年构思并在三年后出版。在该算法中，我们需要不断维护一个包含最短路径树中顶点的集合。在每一步中，我们找到一个尚未在集合内且与源顶点距离最小的顶点，并将其收于集合中。因此，通过Dijkstra算法，我们可以逐步生成一个有序的顶点序列，我们称之为Dijkstra序列。对于一个给定的图，可能有多个Dijkstra序列。例如， { 5 , 1 , 3 , 4 , 2 } \{5,1,3,4,2\} {5,1,3,4,2}和 { 5 , 3 , 1 , 2 , 4 } \{5,3,1,2,4\} {5,3,1,2,4}都是给定图的Dijkstra序列。注意，序列中的第一个顶点即为指定的特定源顶点。你的任务是检查给定的序列是否是$Dijkstra$序列。

输入格式：
第一行包含两个整数$N$和$M$，表示图中点和边的数量。
点的编号$1\sim N$。
接下来$M$行，每行包含三个整数$a,b,c$，表示点$a$和点$b$之间存在一条无向边，长度为$c$。
再一行包含整数$K$，表示需要判断的序列个数。
接下来$K$行，每行包含一个$1\sim N$的排列，表示一个给定序列。

输出格式：
共$K$行，第$i$行输出第$K$个序列的判断，如果序列是Dijkstra序列则输出Yes，否则输出No。

数据范围：
$1\le N\le 1000$,
$1\le M\le 10^5$,
$1\le a,b\le N$,
$1\le c\le 100$,
$1\le K\le 100$,
保证给定无向图是连通图
保证无重边和自环。

对于每次询问，只需要看一下序列中的点是否能被Dijkstra算法的每次循环取到即可。可以用朴素版Dijkstra来做。代码如下：

#include 
#include 
using namespace std;

const int N = 1010, M = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m, K;
int a[N], dist[N];
int g[N][N];
bool vis[N];

bool dijkstra() {
  memset(dist, 0x3f, sizeof dist);
  memset(vis, 0, sizeof vis);
  dist[a[1]] = 0;
  for (int i = 1; i <= n; i++) {
    int t = a[i];
    // 遍历所有最短路未定的点，如果其距离比a[i]的距离更小，
    // 则序列不能是Dijkstra序列，返回false
    for (int j = 1; j <= n; j++)
      if (!vis[j] && dist[j] < dist[t]) return false;

    vis[t] = true;
    for (int j = 1; j <= n; j++)
      dist[j] = min(dist[j], dist[t] + g[t][j]);
  }

  return true;
}

int main() {
  memset(g, 0x3f, sizeof g);
  scanf("%d%d", &n, &m);

  for (int i = 1; i <= n; i++) g[i][i] = 0;
  for (int i = 1; i <= m; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    g[a][b] = g[b][a] = min(g[a][b], c);
  }

  scanf("%d", &K);
  while (K--) {
    for (int i = 1; i <= n; i++)
      scanf("%d", &a[i]);
    
    dijkstra() ? puts("Yes") : puts("No");
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

每次询问时间复杂度$O(n^2)$，空间$O(n)$。