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<stdio.h>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<string>
using namespace std;
char str[16];
map<string,int> m;
vector<pair<int,int> >g[100000];
vector<pair<int,int> >ijk[50000];
pair<int,int> IJK[100000];
vector<int> num[50000];
vector<int> dist[50000];
vector<int> vis[50000];
int VIS[100000];
struct wolf{
	int cost;
	int chg;
	int L;
	int Y;
	wolf(){}
	wolf(int a,int b,int c,int d){
		cost=a;
		chg=b;
		L=c;
		Y=d;
	}
};
inline bool operator<(const wolf&a,const wolf&b){
	if(a.cost!=b.cost)return a.cost>b.cost;
	return a.chg>b.chg;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int v=0;
	scanf("%s",str);
	string S=str;
	scanf("%s",str);
	string T=str;
	m[S]=v++;
	m[T]=v++;
	for(int i=0;i<a;i++){
		int c;
		scanf("%d",&c);
		for(int j=0;j<c;j++){
			scanf("%s",str);
			string STR=str;
			if(m.count(STR)==0)m[STR]=v++;
			ijk[i].push_back(make_pair(999999999,999999999));
			num[i].push_back(m[STR]);
			vis[i].push_back(0);
			g[m[STR]].push_back(make_pair(i,j));
		}
		for(int j=0;j<c-1;j++){
			int d;
			scanf("%d",&d);
			dist[i].push_back(d);
		}
	}
	for(int i=0;i<v;i++)IJK[i]=make_pair(999999999,999999999);
	priority_queue<wolf> Q;
	Q.push(wolf(0,0,-1,m[S]));
	IJK[m[S]]=make_pair(0,0);
	while(Q.size()){
		wolf at=Q.top();
		Q.pop();
		if(at.L==-1){
			if(VIS[at.Y])continue;
			VIS[at.Y]=1;
		}else{
			if(vis[at.L][at.Y])continue;
			vis[at.L][at.Y]=1;
		}
		if(at.L==-1){
			for(int i=0;i<g[at.Y].size();i++){
				int I=g[at.Y][i].first;
				int J=g[at.Y][i].second;
				if(!vis[I][J]&&ijk[I][J]>IJK[at.Y]){
					ijk[I][J]=IJK[at.Y];
					Q.push(wolf(at.cost,at.chg,I,J));
				}
			}
		}else{
			int N=num[at.L][at.Y];
			if(!VIS[N]&&IJK[N]>make_pair(at.cost+b,at.chg+1)){
				IJK[N]=make_pair(at.cost+b,at.chg+1);
				Q.push(wolf(IJK[N].first,IJK[N].second,-1,N));
			}
			if(at.Y&&!vis[at.L][at.Y-1]&&ijk[at.L][at.Y-1]>make_pair(at.cost+dist[at.L][at.Y-1],at.chg)){
				ijk[at.L][at.Y-1]=make_pair(at.cost+dist[at.L][at.Y-1],at.chg);
				Q.push(wolf(at.cost+dist[at.L][at.Y-1],at.chg,at.L,at.Y-1));
			}
			if(at.Y<dist[at.L].size()&&!vis[at.L][at.Y+1]&&ijk[at.L][at.Y+1]>make_pair(at.cost+dist[at.L][at.Y],at.chg)){
				ijk[at.L][at.Y+1]=make_pair(at.cost+dist[at.L][at.Y],at.chg);
				Q.push(wolf(at.cost+dist[at.L][at.Y],at.chg,at.L,at.Y+1));
			}
		}
	}
	if(IJK[m[T]].first==999999999)printf("-1\n");
	else printf("%d %d\n",IJK[m[T]].first-b,IJK[m[T]].second-1);
}