题目描述

样例

C++ 代码

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

const int N = 1010;
int g[N][N];
int dist[N];
bool st[N];
int n, m, k;
int seq[N];

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

    for (int i = 0; i < n; i++)
    {
        int t = -1;
        vector<int> wait;
        for (int j = 1; j <= n; j++)
        {
            if (st[j]) continue;
            if (t == -1 || dist[t] > dist[j])
            {
                t = j;
                wait.clear();
            }
            if (dist[t] == dist[j]) wait.push_back(j);
        }
        bool flag = false;
        for (int j = 0; j < wait.size(); j++)
        {
            if (wait[j] == seq[idx])
            {
                flag = true;
                t = wait[j];
                break;
            }
        }
        if (!flag) return false;
        st[t] = true;
        idx++;
        for (int j = 1; j <= n; j++)
            dist[j] = min(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] = min(g[a][b], c);
    }
    scanf("%d", &k);

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

    return 0;
}