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<vector>
#include<algorithm>
#include<iomanip>
#include<sstream>
#include<map>
#include<queue>
using namespace std;
#define int long long
map<string, int> mp;
vector < vector<int> >g;
vector < vector<int> >c;
vector<vector<int> > list;
signed main() {
	int N, T;
	cin >> N >> T;
	string A, B;
	cin >> A >> B;
	mp[A] = 0;
	mp[B] = 1;
	int M = 2;
	list.resize(M);
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		vector<string> S(a);
		vector<int>t(a - 1);
		int X = g.size();
		for (int j = 0; j < a; j++) {
			cin >> S[j];
			if (mp.count(S[j]) == 0) {
				mp[S[j]] = M;
				M++;
				list.push_back(vector<int>(0));
			}
			list[mp[S[j]]].push_back(X + j);
			g.push_back(vector<int>(0));
			c.push_back(vector<int>(0));
		}
		for (int j = 0; j < a - 1; j++) {
			cin >> t[j];

			g[X + j].push_back(X + j + 1);
			c[X + j].push_back(t[j]);
			g[X + j + 1].push_back(X + j);
			c[X + j + 1].push_back(t[j]);
		}
	}
	int X = g.size();
	for (int i = 0; i < M; i++) {
		g.push_back(vector<int>(0));
		c.push_back(vector<int>(0));
	}
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < list[i].size(); j++) {
			g[list[i][j]].push_back(X + i);
			c[list[i][j]].push_back(0);
			g[X + i].push_back(list[i][j]);
			c[X + i].push_back(T);
		}
	}
	int INF = (int)1 << 60;
	vector<pair<int, int> > dp(g.size(), make_pair(INF, INF));
	dp[X] = make_pair(0, 0);
	priority_queue<pair<pair<int, int>, int> > pq;
	pq.push(make_pair(make_pair(0, 0), X));
	pair<pair<int, int>, int> t;
	int cur = 0;
	pair<int, int>ne;
	while (!pq.empty()) {
		t = pq.top(); pq.pop();
		cur = t.second;
		for (int i = 0; i < g[cur].size(); i++) {
			ne = dp[cur];
			ne.first += c[cur][i];
			if (cur >= X)ne.second++;
			if (dp[g[cur][i]] > ne) {
				dp[g[cur][i]] = ne;
				ne.first = -ne.first;
				ne.second = -ne.second;
				pq.push(make_pair(ne, g[cur][i]));
			}
		}
	}

	//for (auto m : mp) {
	//	cerr << m.first << " " << m.second << endl;
	//}
	//cerr << "X=" << X << endl;
	//for (int i = 0; i < g.size(); i++) {
	//	for (int j = 0; j < g[i].size(); j++) {
	//		cerr << i << " " << g[i][j] << " " << c[i][j] << endl;
	//	}
	//}

	if (dp[X + 1].first < INF) {
		cout << dp[X + 1].first - T << " " << dp[X + 1].second - 1 << endl;
	}
	else {
		cout << -1 << endl;
	}
}