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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
int N,T;
string sA,sB;
int n[50000];
vector<string> vstr[50000];
vector<int> vst[50000],vt[50000];
vector<string> ash;
map<P,P> d;
int main(){
	cin>>N>>T>>sA>>sB;
	rep(i,N){
		cin>>n[i];
		rep(j,n[i]){
			string st;
			cin>>st;
			ash.pb(st);
			vstr[i].pb(st);
		}
		rep(j,n[i]-1){
			int hoge;
			cin>>hoge;
			vt[i].pb(hoge);
		}
	}

	sort(all(ash));
	ash.erase(unique(all(ash)),ash.end());
	rep(i,N) rep(j,n[i]) vst[i].pb(lower_bound(all(ash),vstr[i][j])-ash.begin());
	int A=lower_bound(all(ash),sA)-ash.begin();
	int B=lower_bound(all(ash),sB)-ash.begin();

	vector<P> stats[100000];
	rep(i,N) rep(j,n[i]) stats[vst[i][j]].pb(P(i,j));

	priority_queue<PP,vector<PP>,greater<PP> > que;
	que.push(PP(P(-T,-1),P(-1,A)));
	d[P(-1,A)]=P(-T,-1);
	while(!que.empty()){
		PP pp=que.top();
		que.pop();
		P v=pp.sc;
		P dis=pp.fs;
		if(d[v]!=dis) continue;
		if(v.fs<0){	//name
			int x=v.sc;
			for(P nv:stats[x]){
				P ndis=dis;
				ndis.fs+=T,ndis.sc++;
				if(!d.count(nv) || ndis<d[nv]){
					d[nv]=ndis;
					que.push(PP(ndis,nv));
				}
			}
		}else{	//place
			int x=v.fs,y=v.sc;
			{
				int id=vst[x][y];
				P nv=P(-1,id);
				P ndis=dis;
				if(!d.count(nv) || ndis<d[nv]){
					d[nv]=ndis;
					que.push(PP(ndis,nv));
				}
			}
			if(y-1>=0){
				P nv=P(x,y-1);
				P ndis=dis;
				ndis.fs+=vt[x][y-1];
				if(!d.count(nv) || ndis<d[nv]){
					d[nv]=ndis;
					que.push(PP(ndis,nv));
				}
			}
			if(y+1<n[x]){
				P nv=P(x,y+1);
				P ndis=dis;
				ndis.fs+=vt[x][y];
				if(!d.count(nv) || ndis<d[nv]){
					d[nv]=ndis;
					que.push(PP(ndis,nv));
				}
			}
		}
	}
	P dest=P(-1,B);
	if(!d.count(dest)) puts("-1");
	else cout<<d[dest].fs<<" "<<d[dest].sc<<endl;
}