ABC197F

atcoder.jp

問題文を言い換えます。

"""
最初は頂点１と頂点Nにコマが一つずつ置かれています。

一回の行動で、２つのコマを辺を使って同時に移動させます。

ただし、どちらも同じアルファベットのかかれた辺を使う必要があります。
"""

ここがわかればもう解けたも同然！（だよね…？）

結構簡単なBFSの実装で通りま〜す

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,m,a,b,iti=0;
  char s;
  cin >> n >> m;
  vector<vector<pair<int,char>>>graph(n);
  for(int i=0;i<m;i++){
    cin >> a >> b >> s;
    graph[a-1].push_back(make_pair(b,s));
    graph[b-1].push_back(make_pair(a,s));
  }
  vector<vector<int>>dp(n,vector<int>(n,1e9));
  dp[0][n-1]=0;
  vector<pair<int,int>>stack;
  stack.push_back(make_pair(1,n));
  int ans=1e9;
  while(stack.size()>iti){
    a=stack[iti].first;
    b=stack[iti].second;
    for(int i=0;i<graph[a-1].size();i++)for(int j=0;j<graph[b-1].size();j++){
	if(graph[a-1][i].second!=graph[b-1][j].second)continue;
	//交差する場合
	if(graph[a-1][i].first==b && graph[b-1][j].first==a)ans=min(ans,dp[min(a,b)-1][max(a,b)-1]+1);
	if(dp[min(graph[a-1][i].first,graph[b-1][j].first)-1][max(graph[a-1][i].first,graph[b-1][j].first)-1]<=dp[min(a,b)-1][max(a,b)-1]+2)continue;
	dp[min(graph[a-1][i].first,graph[b-1][j].first)-1][max(graph[a-1][i].first,graph[b-1][j].first)-1]=dp[min(a,b)-1][max(a,b)-1]+2;
	stack.push_back(make_pair(graph[a-1][i].first,graph[b-1][j].first));
      }
    iti++;
  }
  for(int i=0;i<n;i++)ans=min(ans,dp[i][i]);
  if(ans>=1e9)cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}