スイッチを \(2\) 回押すと元の状態に戻るので、

（いまいる頂点, これまでにスイッチを押した回数を \(2\) で割ったあまり)

の組によって現在の状態が表現できます。

はじめは、スイッチを \(0\) 回押した状態で頂点 \(1\) にいるので、状態\((1, 0)\) です。 そこから、「移動」や「スイッチを押す」の行動を行うたびに現在の状態が別の状態に遷移していきます。 そして、最終的に \((N, 0)\) と \((N, 1)\) のどちらかの状態になるまでに行う移動の回数の最小値が本問題の答えです。

入力で与えられるグラフ \(G\) に対し、 「各状態を頂点とし、\(1\) 回の行動で互いに遷移可能な状態間に辺を張った無向グラフ \(G'\) 」を考え、\(G'\) 上の最短経路問題に帰着して本問題を解きます。 つまり、\(G'\) として \((1, 0), (2, 0), \ldots, (N, 0)\) および \((1, 1), (2, 1), \ldots, (N, 1)\) という \(2N\) 個の状態を頂点とし、下記の通りに辺を張って得られる無向グラフを考えます。

• 「移動」の行動に対応して、\(G\) の各辺 \(\lbrace u_i, v_i \rbrace\) ごとに、\(G'\) にコスト \(1\) の無向辺 \(\lbrace (u_i, 1-a_i), (v_i, 1-a_i)\rbrace\) を張る。

• 「スイッチを押す」の行動に対応して、スイッチがある \(G\) の頂点 \(s_i\) ごとに、\(G'\) にコスト \(0\) の無向辺 \(\lbrace (s_i, 0), (s_i, 1)\rbrace\) を張る。

本問題の答えは、\(G'\) 上における \((1, 0)\) から \((N, 0)\) と \((N, 1)\) （のうち近い方）への最短距離となります。（ただし、\((N, 0)\) にも \((N, 1)\) にも到達できなければ答えは \(-1\) ） よって、ダイクストラ法を用いれば \(O(N+M\log N)\) 時間、01BFS を用いれば \(O(N+M)\) 時間で本問題を解くことができます。

以下に、C++ 言語による本問題の正解例を記載します。

#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;
}