题目描述

样例

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

算法1

(Dijkstra模拟) $O(n^2)$

1.通读题目后不难发现这题与Dijkstra算法有密不可分的关系
先给出Dijkstra算法的模板

2.题目要求判断给定的一个序列是都满足Dijkstra算法扩张的顺序，因此我们模拟一下，并且判断每次加入点距离当前集合的长度是否与Dijkstra算法扩张时相同即可。
3.在模拟时，我们同样每次取出图中离源点最近的一个点，判断一下，与给序列中对应的点到源点距离是否相等
(1) 若相等，则维护一下当前图中所有点到源点的距离，与Dijkstra算法中一样。
(2) 不相等，直接返回false，表示当前序列不是一个Dijkstra sequence。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1010;
int g[N][N], q[N], dist[N];
int n, m;
bool st[N];

bool check(int u)
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[u] = 0;

    for(int i = 0; i < n; i ++)
    {
        int minv = 0x3f, t = -1;
        for(int j = 1; j <= n; j ++)
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j])) 
            {
                t = j;
                minv = dist[j];//找到当前离源点最小的值
            }
        }

        st[t] = true;
        if(dist[t] != dist[q[i]]) return false;

        for(int j = 1; j <= n; j ++)
        {
            if(dist[j] > dist[t] + g[t][j])
            {
                dist[j] = dist[t] + g[t][j];
            }
        }
    }

    return true;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int k;
    cin >> k;
    while(k -- )
    {
        for(int i = 0; i < n; i ++) scanf("%d", &q[i]);

        if(check(q[0])) puts("Yes");
        else puts("No");
    }
    return 0;
}