Dijkstra序列（暑假每日一题 5）

$Dijkstra$ 算法是非常著名的贪心算法之一。

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

它由计算机科学家 $EdsgerW.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 序列，系列中依次每个点距离原来的距离是逐渐递增的（不递减序列）

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1010;

int n, m;
int g[N][N], q[N], d[N];
bool st[N];

bool is_dijkstra(){
    
    
    memset(d, 0x3f, sizeof d);
    memset(st, 0, sizeof st);    
    d[q[0]] = 0;
    
    for(int i = 0; i < n; i++){
    
        
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
                
        st[t] = true;
        for(int j = 1; j <= n; j++)
            d[j] = min(d[j], d[t] + g[t][j]);
    }
    
    int last = -1;
    for(int i = 0; i < n; i++)
        if(d[q[i]] < last) return false;
        else last = d[q[i]];
        
    return true;
}

int main(){
    
    
    memset(g, 0x3f, sizeof g);
    
    scanf("%d%d", &n, &m);
    
    int a, b, w;
    for(int i = 0; i < m; i++){
    
        scanf("%d%d%d", &a, &b, &w);
        g[a][b] = g[b][a] = min(g[a][b], w);
    }
    
    int k;
    scanf("%d", &k);
    while(k--){
    
        
        for(int i = 0; i < n; i++)
            scanf("%d", &q[i]);
            
        if(is_dijkstra()) puts("Yes");
        else puts("No");
    }
    
    return 0;
}