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<map>
#include<queue>
#include<cstdio>
#include<string>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

pair<int,int> operator-(const pair<int,int> &a){ return make_pair(-a.first,-a.second); }

int main(){
	map<string,int> f;
	int n,T; scanf("%d%d",&n,&T);
	char tmp[16];
	scanf("%s",tmp); if(f.count(tmp)==0) f.insert(make_pair(tmp,f.size()));
	int s=f[tmp];
	scanf("%s",tmp); if(f.count(tmp)==0) f.insert(make_pair(tmp,f.size()));
	int g=f[tmp];

	int N=0;
	static int idx1[100000],idx2[100000]; // vertex id -> どの路線か, 路線の何番目の駅か
	static vector<int> route[50000],t[50000];
	rep(i,n){
		int m; scanf("%d",&m);
		route[i].resize(m);
		t[i].resize(m-1);
		rep(j,m){
			scanf("%s",tmp); if(f.count(tmp)==0) f.insert(make_pair(tmp,f.size()));
			route[i][j]=f[tmp];
			idx1[N]=i;
			idx2[N]=j;
			N++;
		}
		rep(j,m-1){
			scanf("%d",&t[i][j]);
		}
	}

	static vector<int> V[100000]; // V[i] := { u | route[idx1[u]][idx2[u]] == i }
	rep(u,N) V[route[idx1[u]][idx2[u]]].push_back(u);

	static pair<int,int> d[100000][2]; // <time,乗り換え回数>
	rep(u,N) rep(dir,2) d[u][dir].first=INF;

	static bool trans[100000]; // trans[i] := ( 駅 i から乗換えをしたかどうか ) <- これがないと |E|=O(V^2) となり TLE する

	pair<int,int> ans(-1,0);
	priority_queue< pair< pair<int,int>,pair<int,int> > > Q; // <<-time,-乗り換え回数>,<vertex id,順方向か逆方向か>>
	rep(u,N) if(route[idx1[u]][idx2[u]]==s) {
		d[u][0]=d[u][1]=make_pair(0,0);
		Q.push(make_pair(make_pair(0,0),make_pair(u,0)));
		Q.push(make_pair(make_pair(0,0),make_pair(u,1)));
	}
	while(!Q.empty()){
		pair<int,int> d_now=-Q.top().first;
		int u=Q.top().second.first,dir=Q.top().second.second; Q.pop();

		if(d[u][dir]<d_now) continue;

		if(route[idx1[u]][idx2[u]]==g){ ans=d_now; break; }

		// 今の電車に乗り続ける
		if(dir==0){ // 順方向
			if(idx2[u]+1<route[idx1[u]].size()){
				pair<int,int> d_next=d_now;
				d_next.first+=t[idx1[u]][idx2[u]];
				if(d[u+1][dir]>d_next){
					d[u+1][dir]=d_next;
					Q.push(make_pair(-d_next,make_pair(u+1,dir)));
				}
			}
		}
		else{ // 逆方向
			if(idx2[u]-1>=0){
				pair<int,int> d_next=d_now;
				d_next.first+=t[idx1[u]][idx2[u]-1];
				if(d[u-1][dir]>d_next){
					d[u-1][dir]=d_next;
					Q.push(make_pair(-d_next,make_pair(u-1,dir)));
				}
			}
		}

		// 乗り換え
		if(!trans[route[idx1[u]][idx2[u]]]){
			trans[route[idx1[u]][idx2[u]]]=true;

			rep(i,V[route[idx1[u]][idx2[u]]].size()){
				int v=V[route[idx1[u]][idx2[u]]][i];
				pair<int,int> d_next=d_now;
				d_next.first+=T;
				d_next.second++;
				rep(dir2,2){
					if(d[v][dir2]>d_next){
						d[v][dir2]=d_next;
						Q.push(make_pair(-d_next,make_pair(v,dir2)));
					}
				}
			}
		}
	}

	if(ans.first==-1) puts("-1"); else printf("%d %d\n",ans.first,ans.second);

	return 0;
}