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<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long  ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
typedef vector<int> vec;

typedef pair<int, P> vert;
typedef pair<int, vert> speP;
map<string, int> mp;
map<vert, vector<pair<vert,int>>> G;
map<vert, int> dist,rdist,tnum;
map<vert, bool> visited,rvisited,tvisited;
priority_queue<speP, vector<speP>, greater<speP>> q;
void solve() {
	int n, t;
	cin >> n >> t;
	string a, b; cin >> a >> b;
	mp[a] = 1, mp[b] = 2;
	int cur = 3;
	rep(i, n) {
		int l; cin >> l;
		vector<int> ids;
		rep(j, l) {
			string u; cin >> u;
			if (!mp[u]) {
				mp[u] = cur; cur++;
			}
			ids.push_back(mp[u]);
		}
		rep(j, l - 1) {
			int c; cin >> c;
			G[{ids[j], { i,j }}].push_back({ {ids[j + 1],{i,j + 1}},c });
			G[{ids[j + 1], { i,j + 1 }}].push_back({ { ids[j],{i,j} },c });
		}
		rep(j, l) {
			G[{ids[j], { i,j }}].push_back({ {ids[j],{-1,-1}},t });
			G[{ids[j], { -1,-1 }}].push_back({ { ids[j],{i,j} },0 });
		}
	}
	visited[{1, { -1,-1 }}] = true;
	dist[{1, { -1,-1 }}] = 0;
	q.push({ 0,{1,{-1,-1}} });
	while (!q.empty()) {
		speP p = q.top(); q.pop();
		if (p.first > dist[p.second])continue;
		vector<pair<vert,int>> &g = G[p.second];
		rep(j, g.size()) {
			vert to = g[j].first;
			int nd = p.first + g[j].second;
			if (!visited[to]) {
				visited[to] = true;
				dist[to] = mod;
			}
			if (nd < dist[to]) {
				dist[to] = nd;
				q.push({ nd,to });
			}
		}
	}
	if (!visited[{2, { -1,-1 }}]) {
		cout << -1 << endl; return;
	}
	rvisited[{2, { -1,-1 }}] = true;
	rdist[{2, { -1,-1 }}] = 0;
	q.push({ 0,{2,{-1,-1}} });
	while (!q.empty()) {
		speP p = q.top(); q.pop();
		if (p.first > rdist[p.second])continue;
		vector<pair<vert, int>> &g = G[p.second];
		rep(j, g.size()) {
			vert to = g[j].first;
			int nd = p.first + g[j].second;
			if (!rvisited[to]) {
				rvisited[to] = true;
				rdist[to] = mod;
			}
			if (nd < rdist[to]) {
				rdist[to] = nd;
				q.push({ nd,to });
			}
		}
	}
	int ma = dist[{2, { -1,-1 }}] - t;
	tnum[{1, { -1,-1 }}] = 0;
	tvisited[{1, { -1,-1 }}] = true;
	q.push({ 0,{1,{-1,-1}} });
	while (!q.empty()) {
		speP p = q.top(); q.pop();
		if (p.first > tnum[p.second])continue;
		vector<pair<vert, int>> &g = G[p.second];
		rep(j, g.size()) {
			vert to = g[j].first;
			int hantei = ma;
			if (to.second.first == -1)hantei += t;
			if (dist[p.second] + rdist[to] + g[j].second != hantei)continue;
			int cost = 0;
			if (p.second.second.first != to.second.first)cost = 1;
			int nd = p.first + cost;
			if (!tvisited[to]) {
				tvisited[to] = true;
				tnum[to] = mod;
			}
			if (nd < tnum[to]) {
				tnum[to] = nd;
				q.push({ nd,to });
			}
		}
	}
	/*if (!tvisited[{2, -1}]) {
		cout << "???" << endl;
	}*/
	int mi = tnum[{2, { -1,-1 }}];
	//cout << mi << endl;
	mi = mi / 2 - 1;
	cout << ma << " " << mi << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(5);
	//while (cin >> w>>h>>n,n)solve();
	solve();
	//stop
	return 0;
}