Submission #35557346

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const int maxN = 100011;

int n, m, k, x, y;
int a[maxN], b[maxN];
int best[maxN];
vector<int> adj[maxN];
priority_queue< pair<int, int> > heap;

int main()
{
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    adj[x].pb(y);
    adj[y].pb(x);
  }

  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    best[i] = k;
  }

  for (int i = 1; i <= k; i++) 
    cin >> b[i];
  b[k + 1] = -1;

  best[1] = (a[1] == b[1]) ? 1 : 0;
  heap.push(mp(-best[1], 1));
  
  while (!heap.empty()) {
    const auto [val, node] = heap.top();
    heap.pop();

    int curr = -val;
    if (curr != best[node]) continue;

    for (auto to: adj[node]) {
      int new_best = best[node] + (a[to] == b[curr + 1] ? 1 : 0);
      if (new_best < best[to]) {
        best[to] = new_best;
        heap.push(mp(-new_best, to));
      }
    }
  }

  if (best[n] == k)
    cout << "Yes\n";
  else
    cout << "No\n";

  for (int i = 1; i <= n; i++)
    cerr << best[i] << ' ';
 



  return 0;
}

Submission Info

Judge Result