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;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const ll INF = LLONG_MAX / 10;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int n, t, src, dst, V;
map<string, int> id;

vector<vi> stations;
vector<vi> cost;
vector<vector<pii>> change;
typedef pair<ll, int> Weight;


int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	string ss, sd;
	cin >> n >> t >> ss >> sd;
	id[ss] = 0; id[sd] = 1;
	src = 0, dst = 1;
	V = 2;
	stations.resize(n);
	cost.resize(n);
	change.resize(2);
	REP(i, n)
	{
		int a; cin >> a;
		REP(j, a)
		{
			string s; cin >> s;
			if (!id.count(s))
			{
				id[s] = V;
				V++;
				change.resize(V);
			}
			stations[i].push_back(id[s]);
			change[id[s]].emplace_back(i, j);
		}
		REP(j, a - 1)
		{
			int t; cin >> t;
			cost[i].push_back(t);
		}
	}

	
	//vector<Weight> d(V, Weight(INF, 1e9));
	vector<vector<Weight>> d(n);
	REP(i, n)
	{
		d[i].resize(stations[i].size(), Weight(INF, 1e9));
	}
	vector<bool> used(V);
	priority_queue<pair<Weight, pii>, vector<pair<Weight, pii>>, greater<pair<Weight, pii>>> que;
	for(auto i: change[0])
	{
		d[i.first][i.second] = Weight(0, 0);
		que.emplace(make_pair(Weight(0, 0), i));
	}
	while (!que.empty())
	{
		Weight w = que.top().first;
		int rosen = que.top().second.first;
		int pos = que.top().second.second;
		que.pop();
		int tmp = stations[rosen][pos];
		if (d[rosen][pos] < w) continue;
		if (pos != 0)
		{
			int ct = cost[rosen][pos-1];
			if (d[rosen][pos-1] > Weight(w.first + ct, w.second))
			{
				d[rosen][pos-1] = Weight(w.first + ct, w.second);
				que.emplace(make_pair(d[rosen][pos - 1], pii(rosen, pos - 1)));
			}
		}
		if (pos != stations[rosen].size() - 1)
		{
			int ct = cost[rosen][pos];
			if (d[rosen][pos + 1] > Weight(w.first + ct, w.second))
			{
				d[rosen][pos + 1] = Weight(w.first + ct, w.second);
				que.emplace(make_pair(d[rosen][pos + 1], pii(rosen, pos + 1)));
			}
		}
		if (!used[tmp])
		{
			used[tmp] = true;
			for (auto i : change[tmp])
			{
				if (d[i.first][i.second] > Weight(w.first + t, w.second + 1))
				{
					d[i.first][i.second] = Weight(w.first + t, w.second + 1);
					que.emplace(make_pair(d[i.first][i.second], pii(i.first, i.second)));
				}
			}
		}
	}
	Weight ans(INF, 1e9);
	for (auto i : change[dst]) chmin(ans, d[i.first][i.second]);
	if (ans.first >= INF) cout << -1 << endl;
	else cout << ans.first << " " << ans.second << endl;
	return 0;
}