4275. Dijkstra序列

思路:直接跑一遍dijkstra看是否与序列中加入的顶点顺序相同

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;

int dis[N],g[N][N];
bool st[N];
int q[N];
int n,m;
bool dijkstra(){
    
    memset(st, false, sizeof st);
    memset(dis, INF, sizeof dis);
    dis[q[0]] = 0;
    
    
    for(int i = 0; i < n; i++){
    
        
        int t=q[i];
        for(int j = 1; j <= n; j++)
            if(!st[j] && dis[j] < dis[t])
                return false;
        st[t] = true;
        for(int j = 1; j <=n; j++)
            dis[j] = min(dis[j],dis[t] + g[t][j]);
        
        
    }
    return true;
}


int main()
{
    
    
    scanf("%d%d", &n, &m);
    memset(g, INF, 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;
}