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 <vector>
#include <string>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <sstream>
#include <algorithm>
#include <map>
#define INF 2000000005
using namespace std;
typedef pair<int,int> P;
struct edge{
	int t,cost;
	edge(){}
	edge(int tt,int cc){
		t=tt;
		cost=cc;
	}	
};

struct eel{
	int v,cost,tra;
	eel(){}
	eel(int vv,int cc,int tt){
		v=vv;
		cost=cc;
		tra=tt;
	}
	bool operator<(const eel &e)const{
		if(cost==e.cost)return tra>e.tra;
		return cost>e.cost;
	}
};


int n,t;
int all;
int id[100001];
bool transfer[100001];
P dist[100001];
vector<int> same[100001];
vector<edge> G[100001];
map<string,int> data;

P dijk(int start,int goal){
	priority_queue<eel> que;
	memset(transfer,false,sizeof(transfer));
	for(int i=0;i<all;i++){
		dist[i].first=INF;
		dist[i].second=INF;
	}
	for(int i=0;i<same[start].size();i++){
		que.push(eel(same[start][i],0,0));
		dist[same[start][i]]=P(0,0);
	}
	transfer[start]=true;
	while(que.size()){
		eel q=que.top();
		que.pop();
		if(dist[q.v].first<q.cost || dist[q.v].second<q.tra)continue;
		if(id[q.v]==goal)return P(q.cost,q.tra);
		for(int i=0;i<G[q.v].size();i++){
			edge e=G[q.v][i];
			if(dist[e.t].first>q.cost+e.cost || (dist[e.t].first==q.cost+e.cost && dist[e.t].second>q.tra)){
				dist[e.t]=P(q.cost+e.cost,q.tra);
				que.push(eel(e.t,q.cost+e.cost,q.tra));
			}
		}
		if(!transfer[id[q.v]]){
			transfer[id[q.v]]=true;
			for(int i=0;i<same[id[q.v]].size();i++){
				int next=same[id[q.v]][i];
				if(next==q.v)continue;
				dist[next]=P(q.cost+t,q.tra+1);
				que.push(eel(next,q.cost+t,q.tra+1));
			}
		}
	}
	return P(-1,-1);
}

int main(void){
	scanf("%d%d%*c",&n,&t);
	string str;
	string A;
	string B;
	getline(cin,str);
	istringstream stream(str);
	getline(stream,A,' ');
	getline(stream,B);
	for(int i=0;i<n;i++){
		int a;
		scanf("%d%*c",&a);
		int prev=all;
		getline(cin,str);
		istringstream stream(str);
		string name;
		while(getline(stream,name,' ')){
			if(data.find(name)==data.end()){
				int next=data.size();
				data[name]=next;
			}
			id[all]=data[name];
			same[data[name]].push_back(all);
			all++;
		}
		for(int j=0;j<a-1;j++){
			int tt;
			scanf("%d%*c",&tt);
			G[prev+j].push_back(edge(prev+j+1,tt));
			G[prev+j+1].push_back(edge(prev+j,tt));
		}
	}
	P res=dijk(data[A],data[B]);
	if(res.first==-1)printf("-1\n");
	else printf("%d %d\n",res.first,res.second);
	return 0;
}