Problem: Example

Input

2 10
Warsaw Petersburg
3
Kiev Moscow Petersburg
150 120
3
Moscow Minsk Warsaw
100 150


Output

380 1

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
using namespace std;
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2371&lang=jp
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60
struct edge {
	int u;
	int v;
	int route;
	int time;
	edge() {}
	edge(int u, int v, int r, int t) :u(u), v(v), route(r), time(t) {}
};

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N, T; cin >> N >> T;
	map<string, int> mp;
	int cnt = 0;
	string A, B; cin >> A >> B;
	mp[A] = cnt; cnt++;
	mp[B] = cnt; cnt++;
	vector<vector<ll>> S(N), Time(N);
	for (int i = 0; i < N;i++) {
		ll a; cin >> a;
		for (int j = 0; j < a;j++) {
			string s; cin >> s;
			if (mp.count(s) != 0) { S[i].push_back(mp[s]); }
			else { mp[s] = cnt; S[i].push_back(cnt); cnt++; }
		}
		for (int j = 0; j < a - 1;j++) {
			ll t; cin >> t; Time[i].push_back(t);
		}
	}

	vector<vector<pii>> Change(cnt);
	for (int i = 0; i < N;i++) {
		for (int j = 0; j < (int)S[i].size();j++) {
			Change[S[i][j]].push_back({ i,j });
		}
	}

	vector<vector<pll>> dist(N);
	for (int i = 0; i < N;i++) {
		dist[i].resize(S[i].size(), { LINF,LINF });
	}
	vector<int> checked(cnt);
	using Key = pair<pll, pll>;
	priority_queue<Key, vector<Key>, greater<Key>> q;
	for (auto e : Change[0]) {
		dist[e.first][e.second] = { 0,0 };
		q.emplace(make_pair(pll(0, 0), e));
	}
	while (!q.empty()) {
		auto pp = q.top(); q.pop();
		auto d = pp.first;
		int route = pp.second.first;
		int pos = pp.second.second;
		int station = S[route][pos];
		if (dist[route][pos] < d) continue;

		/* same route / rev */
		if (pos != 0) {
			int time = Time[route][pos - 1];
			if (dist[route][pos - 1] > make_pair(d.first + time, d.second)) {
				dist[route][pos - 1] = { d.first + time,d.second };
				q.emplace(make_pair(dist[route][pos - 1], pll(route, pos - 1)));
			}
		}
		/* same route / ad */
		if (pos != S[route].size() - 1) {
			int time = Time[route][pos];
			if (dist[route][pos + 1] > make_pair(d.first + time, d.second)) {
				dist[route][pos + 1] = { d.first + time,d.second };
				q.emplace(make_pair(dist[route][pos + 1], pll(route, pos + 1)));
			}
		}
		/* change route */
		if (checked[station] == 0) {
			checked[station] = 1;
			for (auto e : Change[station]) {
				if (dist[e.first][e.second] > make_pair(d.first + T, d.second + 1)) {
					dist[e.first][e.second] = { d.first + T,d.second + 1 };
					q.emplace(make_pair(dist[e.first][e.second], pll(e.first, e.second)));
				}
			}
		}
	}
	pll ans = { LINF,LINF };
	for (auto e : Change[1]) ans = min(ans, dist[e.first][e.second]);
	if (ans.first >= LINF) cout << -1 << endl;
	else cout << ans.first << " " << ans.second << endl;
	return 0;
}