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

题目思路

• 注意审题 Orz：检查序列是否为 Dijkstra 过程中 每次找到 距离原点最近 用于更新相邻点 的 中介点 的 序列
• Dijkstra 每次找目前距原点最近的点，若有几个距离相同的会取其中一个，但其实先检查另外几个点也可
• 整体模板还是用 Dijkstra，每次循环检查 query 的一位
  • 查 当前距离原点最近 的 未访问点 与原点的距离
  • 看 与当前位的 query 中的点 到原点的距离是否符合
  • 若符合，则以 query 当前点为中介 更新邻接点距原点的距离
  • 若不符合，说明此时不应当以 query 当前点为中介继续 Dijkstra，即此 query 非所要求的 Dijkstra sequence，返回 false

AC代码

#include<iostream>
using namespace std;
const int INF = 0x3fffffff;
int n, G[1001][1001], d[1001], query[1001];
bool Dijkstra(int root){
    fill(d, d+1001, INF);
    bool vis[1001] = {false};
    d[root] = 0;
    for (int i = 0; i < n; i++){
        int u, min = INF;
        for (int j = 1; j < n + 1; j++)
            if (d[j] < min && !vis[j])
                min = d[j];
        if (d[query[i]] == min) u = query[i];
        else return false;
        vis[u] = true;
        for (int j = 1; j < n + 1; j++)
            if (G[u][j] && !vis[j] && d[j] > d[u] + G[u][j])
                d[j] = d[u] + G[u][j];
    }
    return true;
}
int main()
{
    int m, u, v, distance, k;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++){
        scanf("%d%d%d", &u, &v, &distance);
        G[u][v] = G[v][u] = distance;
    }
    scanf("%d",&k);
    for (int i = 0; i < k; i++){
        for (int j = 0; j < n; j++) scanf("%d", &query[j]);
        bool isD = Dijkstra(query[0]);
        printf("%s\n", isD ? "Yes" : "No");
    }
    return 0;
}