Codeforces Round #333 (Div. 1) A. The Two Routes

問題

Problem - A - Codeforces
頂点数n(n<=400)の無向グラフが与えられる。
各辺は線路が敷かれていることを意味し、電車が移動することが出来る。
また、ある2つの頂点について間に線路が敷かれていない時、その間には道路があり、車が移動できる。
電車も車も頂点1にいる状態から頂点nを目指して同時に出発し、1つの辺を移動するのに1時間がかかる。
ただし、頂点n以外の頂点に留まっていることはできない。
更に、危険なので、電車と車が同じ時刻に同じ頂点にいてはいけない。

電車と車がどちらも頂点nに到着するまでの最小時間を求めよ。

解法

どちらかの乗り物は頂点1から頂点nへの直接的なルートを持っているので、もう片方についてダイクストラ。

実装

#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 400;

struct State
{
	int v, cost;
	State() {}
	State(int _v, int _cost) : v(_v), cost(_cost) {}
	bool operator < (const State &d) const
	{
		return cost > d.cost;
	}
};

int N, M;
vector< vector<int> > e, f;

int Solve(vector< vector<int> > &e)
{
	bool isVisited[MAX_N] = {};
	queue<State> q;
	q.push(State(0, 0));
	while (!q.empty())
	{
		State t = q.front(); q.pop();
		if (isVisited[t.v]) continue;
		isVisited[t.v] = true;
		for (int i = 0; i < e[t.v].size(); i++)
		{
			if (e[t.v][i] == N - 1) return t.cost + 1;
			q.push(State(e[t.v][i], t.cost + 1));
		}
	}
	return -1;
}

signed main()
{
	cin >> N >> M;
	e.resize(N); f.resize(N);
	bool exists[MAX_N][MAX_N] = {};
	for (int i = 0; i < M; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v); u--; v--;
		exists[u][v] = exists[v][u] = true;
		e[u].push_back(v); e[v].push_back(u);
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			if (exists[i][j] || exists[j][i]) continue;
			f[i].push_back(j); f[j].push_back(i);
		}
	}
	printf("%d\n", Solve(exists[0][N - 1] ? f : e));
	return 0;
}