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:
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-9;

ll d[200000];
vector<edge> G[200000];
vector<string> st;

void f(int u, int v, ll w) {
	edge e = {u, v, w};
	G[u].push_back(e);
}

int g(string s) {
	return lower_bound(st.begin(), st.end(), s) - st.begin();
}

void dijkstra(int n, vector<edge> G[], int s, ll d[]) {
	fill(d, d + n, LLONG_MAX); d[s] = 0;
	priority_queue<ll_i, vector<ll_i>, greater<ll_i> > q;
	q.push(ll_i(0, s));
	while (!q.empty()) {
		ll_i p = q.top(); q.pop();
		int u = p.second;
		if (p.first > d[u]) continue;
		for (int i = 0; i < G[u].size(); i++) {
			edge e = G[u][i];
			if (d[e.v] > d[u] + e.w) {
				d[e.v] = d[u] + e.w;
				q.push(ll_i(d[e.v], e.v));
			}
		}
	}
}

int main() {
	int N, T; cin >> N >> T;
	string A, B; cin >> A >> B;
	vector<int> a(N);
	vector<vector<string> > s(N);
	vector<vector<int> > t(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		s[i].resize(a[i]);
		for (int j = 0; j < a[i]; j++)
			cin >> s[i][j];
		t[i].resize(a[i] - 1);
		for (int j = 0; j + 1 < a[i]; j++)
			cin >> t[i][j];
	}
	st.push_back(A);
	st.push_back(B);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < a[i]; j++)
			st.push_back(s[i][j]);
	sort(st.begin(), st.end());
	st.erase(unique(st.begin(), st.end()), st.end());
	int n = st.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < a[i]; j++) {
			int u = g(s[i][j]);
			f(u, n + j, T*1000000+1);
			f(n + j, u, 0);
		}
		for (int j = 0; j + 1 < a[i]; j++) {
			f(n + j, n + j + 1, t[i][j]*1000000);
			f(n + j + 1, n + j, t[i][j]*1000000);
		}
		n += a[i];
	}
	dijkstra(n, G, g(A), d);
	ll ans = d[g(B)];
	if (ans == LLONG_MAX) {
		cout << -1 << endl;
		return 0;
	}
	cout << ans / 1000000 - T << ' ' << ans % 1000000 - 1 << endl;
}