Since hitting switches twice end up in the original state, we can express the current state by the following pair:

(the current vertex, the remainder when the number of hits so far is divided by \(2\)).

Initially, Takahashi is at vertex \(0\), where he has hit the switch \(0\) times so far, so he is in a state \((1, 0)\). Every time he make a Move or a Hit Switch, the current state transitions to another. The answer to this problem is obtained as the number of Moves until the state finally reaches either \((N, 0)\) or \((N, 1)\).

Given the graph \(G\) in the input. we consider “a undirected graph \(G'\) where each vertex correspond to each state and an edge is added between each pair of states that we can transition between each other,” and boil the original problem down to the shortest path problem on \(G'\). In other words, we consider a undirected graph \(G'\) with \(2N\) vertices \((1, 0), (2, 0), \ldots, (N, 0)\) and \((1, 1), (2, 1), \ldots, (N, 1)\), adding edges as follows:

• corresponding to the action Move, we add an edge \(\lbrace (u_i, 1-a_i), (v_i, 1-a_i)\rbrace\) of cost \(1\) to \(G'\), for each edge \(\lbrace u_i, v_i \rbrace\) of \(G\);

• corresponding to the action Hit Switch, we add an edge \(\lbrace (s_i, 0), (s_i, 1)\rbrace\) of cost \(0\) to \(G'\), for each vertex \(s_i\) of \(G\).

The answer to this problem is the shortest path on \(G'\) from \((1, 0)\) to (nearest of) \((N, 0)\) or \((N, 1)\) (or \(-1\)) if neither is reachable). Therefore, we can solve the problem in a total of \(O(N+M\log N)\) time with Dijkstra’s algorithm, or in \(O(N+M)\) with 01-BFS (Breadth-First Search).

The following is a sample code in C++ language.

#include <iostream>
#include <utility>
#include <vector>
#include <deque>
using namespace std;
typedef pair<int, int> edge;
const int inf = 1e9;

int n, m, k;
vector<edge> G[400005];
int dist[400005];

int main(void)
{
  cin >> n >> m >> k;
  int u, v, a, s;
  for(int i = 1; i <= m; i++){
    cin >> u >> v >> a;
    if(a) G[u].push_back(edge(v, 1)), G[v].push_back(edge(u, 1));
    else G[n+u].push_back(edge(n+v, 1)), G[n+v].push_back(edge(n+u, 1));
  }
  for(int i = 1; i <= k; i++){
    cin >> s;
    G[s].push_back(edge(n+s, 0)), G[n+s].push_back(edge(s, 0));
  }
  
  deque<int> deq;
  deq.push_back(1);
  for(int i = 1; i <= 2*n; i++) dist[i] = inf;
  dist[1] = 0;
  
  while(deq.size()){
    int v = deq.front();
    deq.pop_front();
    for(int i = 0; i < (int)G[v].size(); i++){
      int u = G[v][i].first, c = G[v][i].second;
      if(dist[u] > dist[v] + c){
        dist[u] = dist[v] + c;
        if(c == 0) deq.push_front(u);
        else deq.push_back(u);
      }
    }
  }
  
  int ans = min(dist[n], dist[2*n]);
  if(ans == inf) ans = -1;
  cout << ans << endl;
  
  return 0;
}