4275. Dijkstra sequence

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 Edsger W. 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∼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∼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≤N≤1000,
1≤M≤105,
1≤a,b≤N,
1≤c≤100,
1≤K≤100,
Ensure that a given undirected graph is connected ,
Ensure no double edges and self rings （ The official website didn't mention , But after actual measurement , The official website data meets this condition ）.

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

Code ：

//  Judge whether each step is the current minimum 
#include <bits/stdc++.h>
using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;

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

bool dijkstra()
{
    
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[q[0]] = 0;

    for (int i = 0; i < n; i++)
    {
    
        int t = q[i];
        for (int j = 1; j <= n; j++)
            if (!st[j] && dist[j] < dist[t])
                return false;
        st[t] = true;
        for (int j = 1; j <= n; j++)
        {
    
            if (!st[j] && dist[j] > dist[t] + g[t][j])
                dist[j] = dist[t] + g[t][j];
        }
    }

    return true;
}

int main()
{
    
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    while (m--)
    {
    
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = c;
    }

    int k;
    scanf("%d", &k);
    while (k--)
    {
    
        for (int i = 0; i < n; i++)
            scanf("%d", &q[i]);
        if (dijkstra())
            puts("Yes");
        else
            puts("No");
    }

    return 0;
}