<---大佬们点个赞吧qwq

$$\huge\color{orange}{→→→暑假每日一题2022题解合集←←←}$$
$\ $
$\ $
Dijkstra 算法是非常著名的贪心算法之一。

它用于解决单源最短路径问题，即指定一个特定源顶点，求该顶点到给定图的所有其他顶点的最短路径。

它由计算机科学家 Edsger W. Dijkstra 于 $1956$ 年构思并在三年后出版。

在该算法中，我们需要不断维护一个包含最短路径树中顶点的集合。

在每一步中，我们找到一个尚未在集合内且与源顶点距离最小的顶点，并将其收于集合中。

因此，通过 Dijkstra 算法，我们可以逐步生成一个有序的顶点序列，我们称之为 Dijkstra 序列。

对于一个给定的图，可能有多个 Dijkstra 序列。

例如，$\{ 5, 1, 3, 4, 2 \}$ 和 $\{ 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$,
保证给定无向图是连通图，
保证无重边和自环（官网没提，但是经实测，官网数据符合此条件）。

输入样例：

5 7
1 2 2
1 5 1
2 3 1
2 4 1
2 5 2
3 5 1
3 4 1
4
5 1 3 4 2
5 3 1 2 4
2 3 4 5 1
3 2 1 5 4

输出样例：

Yes
Yes
Yes
No

思路

在每一步中，我们找到一个尚未在集合内且与源顶点距离最小的顶点，并将其收于集合中。

题目描述里的这句话是关键。我们只需要根据这句话改编一下朴素 dijkstra 就行了。

C++代码

#include <iostream>
#include <cstring> // memset头文件

using namespace std;

const int N = 1010; // 最大边数

int n, m, k;
int g[N][N]; // 此题数据范围不大，可以用邻接矩阵来存
int dist[N], s[N]; // dist存距离，s存dijkstra序列
bool st[N]; // st存有没有更新过

bool dijkstra(int x) // 此题数据范围不大，可以直接用朴素dijkstra
{
    memset(dist, 0x3f, sizeof dist); // dist数组初始化为正无穷
    memset(st, 0, sizeof st); // st数组清零
    dist[x] = 0, st[x] = true; // 把起点的数据初始化一下

    for (int i = 1; i <= n; i ++ ) // 按顺序遍历所有序列中的点
    {
        int t = s[i]; // t是这一轮要加入的点
        st[t] = true; // 更新了

        for (int j = 1; j <= n; j ++ )
            if (!st[j] && dist[j] < dist[t]) // 如果还有一个点没被搜过且比它更优
                return false; // 则这个序列不是dijkstra序列

        for (int j = 1; j <= n; j ++ )
            if (dist[t] + g[t][j] < dist[j]) // 如果从起点先到t在到j的距离比原先还要短
                dist[j] = dist[t] + g[t][j]; // 更新dist[j]
    }

    return true; // 所有点都更新完了，这个序列是dijkstra序列
}

int main()
{
    memset(g, 0x3f, sizeof g); // 初始化邻接矩阵

    cin >> n >> m;
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c; // 读入一条边
        g[a][b] = g[b][a] = c; // 由于是无向图，所以要加一条反向边
    }

    cin >> k;
    while (k -- )
    {
        for (int i = 1; i <= n; i ++ ) cin >> s[i]; // 读入序列
        if (dijkstra(s[1])) puts("Yes"); // 如果是dijkstra序列则输出"Yes"
        else puts("No"); // 否则输出"No"
    }

    return 0;
}