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 all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }

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); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000009;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

template<class T>
struct Edge{
	int from,to;
	T cost;
	Edge(int to,T cost) : to(to),cost(cost){}
	Edge(int from,int to,T cost) : from(from),to(to),cost(cost){}
};

template<class T>
using WeightedGraph = vector<vector<Edge<T>>>;
using Graph = vector<vector<int>>;
template<class T>
using Matrix = vector<vector<T>>;

pair<int,int> operator+(pair<int,int> p1,pair<int,int> p2){
	return make_pair(p1.first + p2.first,p1.second + p2.second);
}

template<class T>
vector<T> dijkstra(const WeightedGraph<T> &G,int source = 0){
	using P = pair<T,int>;
	vector<T> dist(G.size(),make_pair(INF,INF));
	priority_queue<P,vector<P>,greater<P>> que;
	dist[source] = make_pair(0,0);
	que.emplace(dist[source],source);
	while(!que.empty()){
		P p = que.top();que.pop();
		int v = p.second;
		if(dist[v] < p.first) continue;
		for(const auto &e : G[v]){
			if(dist[e.to] > dist[v] + e.cost){
				dist[e.to] = dist[v] + e.cost;
				que.emplace(dist[e.to],e.to);
			}
		}
	}
	return dist;
}

signed main(){
	int n,t,c[50010];
	vector<int> ss[50010],ts[50010];
	string a,b;
	map<string,int> name_to_index;
	cin >> n >> t >> a >> b;
	name_to_index[a] = 0;
	name_to_index[b] = 1;
	int index = 2,vs = 0;
	for(int i = 0;i < n;i++){
		cin >> c[i];
		for(int j = 0;j < c[i];j++){
			string s;
			cin >> s;
			if(!name_to_index.count(s)) name_to_index[s] = index++;
			ss[i].push_back(name_to_index[s]);
		}
		for(int j = 0;j < c[i] - 1;j++){
			int d;
			cin >> d;
			ts[i].push_back(d);
		}
		vs += c[i];
	}
	WeightedGraph<pair<int,int>> G(vs + index);
	int v = 0;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < c[i];j++){
			if(j){
				G[v + j - 1].emplace_back(v + j,make_pair(ts[i][j - 1],0));
				G[v + j].emplace_back(v + j - 1,make_pair(ts[i][j - 1],0));
			}
			G[v + j].emplace_back(vs + ss[i][j],make_pair(t,1));
			G[vs + ss[i][j]].emplace_back(v + j,make_pair(0,0));
		}
		v += c[i];
	}
	auto dist = dijkstra(G,vs);
	if(dist[vs + 1].first == INF) cout << -1 << endl;
	else cout << dist[vs + 1].first - t << " " << dist[vs + 1].second - 1 << endl;
}