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<iostream>
#include<string>
#include<functional>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
vector<string>vec[500000], W; vector<int>vec2[500000];
int n, t, num; string a, b; pair<int, int>dist[500000];
vector<pair<int, int>>X[500000];

pair<int, int> dijkstra(string S, string T) {
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>Q;
	int cnt4 = 0; for (int i = 0; i < 500000; i++)dist[i] = make_pair(1069999999, 1069999999);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < vec[i].size(); j++) {
			if (S == vec[i][j]) { Q.push(make_tuple(0, cnt4, 0)); dist[cnt4] = make_pair(0, 0); }
			cnt4++;
		}
	}
	while (!Q.empty()) {
		int a1 = get<0>(Q.top()), a2 = get<1>(Q.top()), a3 = get<2>(Q.top()); Q.pop();
		for (int i = 0; i < X[a2].size(); i++) {
			int to = X[a2][i].first;
			int U = 0; if (a2 >= num)U = 1;
			if (dist[to] > make_pair(a1 + X[a2][i].second, a3 + U)) {
				dist[to] = make_pair(a1 + X[a2][i].second, a3 + U);
				Q.push(make_tuple(dist[to].first, to, dist[to].second));
			}
		}
	}
	cnt4 = 0; pair<int, int> minx = make_pair(2139999999, 2139999999);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < vec[i].size(); j++) {
			if (T == vec[i][j]) { minx = min(minx, dist[cnt4]); }
			cnt4++;
		}
	}
	return minx;
}
int main() {
	cin >> n >> t >> a >> b; int cnt1 = 0;
	for (int i = 0; i < n; i++) {
		int E; cin >> E;
		for (int j = 0; j < E; j++) {
			string W2; cin >> W2; W.push_back(W2);
			vec[i].push_back(W2); cnt1++;
		}
		for (int j = 0; j < E - 1; j++) { int W3; cin >> W3; vec2[i].push_back(W3); }
	}
	int cnt2 = 0; sort(W.begin(), W.end());
	vector<string>V; V.push_back(W[0]); for (int i = 1; i < W.size(); i++) { if (W[i - 1] != W[i])V.push_back(W[i]); }
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < vec2[i].size(); j++) {
			X[cnt2].push_back(make_pair(cnt2 + 1, vec2[i][j]));
			X[cnt2 + 1].push_back(make_pair(cnt2, vec2[i][j]));
			cnt2++;
		}
		cnt2++;
	}
	num = cnt2;
	int cnt3 = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < vec[i].size(); j++) {
			int pos1 = lower_bound(W.begin(), W.end(), vec[i][j]) - W.begin();
			X[cnt2 + pos1].push_back(make_pair(cnt3, 0));
			X[cnt3].push_back(make_pair(cnt2 + pos1, t));
			cnt3++;
		}
	}
	pair<int, int>ans = dijkstra(a, b);
	if (ans.first > 1000000000)cout << "-1" << endl;
	else cout << ans.first << ' ' << ans.second << endl;
	return 0;
}