마이다스 18년 대회 3번

A에서 Z로 이동하는 최단거리를 찾는데

중간에 거점 last를 거쳐서 가는 최단거리를 찾는 문제

#define INT_MAX_ 2100000000;

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <functional>

using namespace std;

int last;
int N;
int dist[27];
vector<pair<int, int>> adj[27];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void dijkstra(int startNode) {

	for (int i = 1; i <= N; i++) {
		dist[i] = INT_MAX_;
	}
	dist[startNode] = 0;

	pq.push(make_pair(0, startNode));
	while (!pq.empty()) {
		int cost = pq.top().first;
		int now = pq.top().second;
		pq.pop();
		if (dist[now] < cost) continue;
		for (pair<int, int> next : adj[now]) {
			if (dist[next.second] > next.first + cost) {
				pq.push(make_pair(next.first + cost, next.second));
				dist[next.second] = next.first + cost;
			}
		}
	}

	return;
}

int main() {
	cin >> N;

	string a;
	for (int i = 0; i < N; i++) {
		cin >> a;
		adj[(a[0] - 'A')].push_back(make_pair<int, int>(1, (a[2] - 'A')));
	}

	cin >> a;
	last = a[0] - 'A';

	dijkstra(0);
	int f1= dist[last];

	for (int i = 0; i < 27; i++) {
		dist[i] = INT_MAX_;
	}
	pq = priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>();

	dijkstra(last);
	int f2 = dist['Z' - 'A'];

	int result = f1 + f2;

	if ((f1 == 2100000000) || (f2 == 2100000000)) {
		cout << -1 << endl;
	}
	else {
		cout << result << endl;
	}
	return 0;
}