Dijkstra sequence (summer vacation daily question 5)

$Dijkstra$ Algorithm is one of the most famous greedy algorithms .

It is used to solve the single source shortest path problem , That is, specify a specific source vertex , Find the shortest path from this vertex to all other vertices of a given graph .

It was developed by computer scientists $EdsgerW.Dijkstra$ On 1956 Conceived in and published three years later .

In this algorithm , We need to constantly maintain a set of vertices in the shortest path tree .

At each step , We find a vertex that is not yet in the set and has the smallest distance from the source vertex , And put it in the collection .

therefore , adopt $Dijkstra$ Algorithm , We can generate an ordered sequence of vertices step by step , We call it $Dijkstra$ Sequence .

For a given graph , There may be more than one $Dijkstra$ Sequence .

for example ,$\{5,1,3,4,2\}$ and $\{5,3,1,2,4\}$ Are all given graphs Dijkstra Sequence .

Be careful , The first vertex in the sequence is the specified source vertex .

Your task is to check whether a given sequence is Dijkstra Sequence .

Input format
The first line contains two integers $N$ and $M$, Represents the number of points and edges in the graph .

Number of points $1\sim N$.

Next $M$ That's ok , Each line contains three integers $a,b,c$, Indication point $a$ Sum point $b$ There is an undirected edge between , The length is $c$.

The next line contains integers $K$, Indicates the number of sequences to be judged .

Next $K$ That's ok , Each line contains a $1\sim N$ Permutation , Represents a given sequence .

Output format
common $K$ That's ok , The first $i$ Line output the $K$ Judgment of sequences , If the sequence is $Dijkstra$ Sequence is output Yes, Otherwise output No.

Data range
$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,$

Ensure that a given undirected graph is connected ,
Ensure no double edges and self rings .

sample input ：

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

sample output ：

Yes
Yes
Yes
No

---

Grasp the essence ：dijkstra Sequence , The distance from each point in the series to the original point is gradually increasing （ Non decreasing sequence ）

#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;
}