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 <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 99999883

struct Data{
	Data(int arg_to,int arg_cost,int arg_line_id,int arg_in_line_index){
		to = arg_to;
		cost = arg_cost;
		line_id = arg_line_id;
		in_line_index = arg_in_line_index;
		min_cost = BIG_NUM;
		min_change_num = BIG_NUM;
	}
	int to,cost,line_id,in_line_index,min_cost,min_change_num;
};

struct STATE{
	STATE(int arg_st_id,int arg_sum_cost,int arg_change_num,int arg_line_id,int arg_in_line_index,int arg_pre_node,int arg_pre_id){
		st_id = arg_st_id;
		sum_cost = arg_sum_cost;
		change_num = arg_change_num;
		line_id = arg_line_id;
		in_line_index = arg_in_line_index;
		pre_node = arg_pre_node;
		pre_id = arg_pre_id;
	}
	bool operator<(const struct STATE &arg) const{
		if(sum_cost != arg.sum_cost){
			return sum_cost > arg.sum_cost;
		}else{
			return change_num > arg.change_num;
		}
	}

	int st_id,sum_cost,change_num,line_id,in_line_index,pre_node,pre_id;
};

map<ull,int> MAP;
vector<Data> G[100000];
int st_index[100000],cost[100000];


ull makeCode(char buf[11]){

	int length;
	for(length = 0; buf[length] != '\0'; length++);

	ull ret = 0;

	for(int i = 0; i < length; i++){
		ret = buf[i] + ret*NUM;
	}
	return ret;
}

int main(){

	int N,T;
	scanf("%d %d",&N,&T);

	ull tmp_code;
	char buf[11];

	int start = 0,goal = 1;

	scanf("%s",buf);
	MAP[makeCode(buf)] = start;

	scanf("%s",buf);
	MAP[makeCode(buf)] = goal;

	int index = 2,tmp,tmp_cost;

	for(int loop = 0; loop < N; loop++){
		scanf("%d",&tmp);

		//まずは駅番号を取得
		for(int i = 0; i < tmp; i++){
			scanf("%s",buf);
			tmp_code = makeCode(buf);

			auto at = MAP.find(tmp_code);

			if(at != MAP.end()){
				st_index[i] = MAP[tmp_code];
			}else{
				MAP[tmp_code] = index;
				st_index[i] = index;
				index++;
			}
		}

		//駅間の距離を取得
		for(int i = 0; i < tmp-1; i++){
			scanf("%d",&tmp_cost);
			G[st_index[i]].push_back(Data(st_index[i+1],tmp_cost,loop,i));
			G[st_index[i+1]].push_back(Data(st_index[i],tmp_cost,loop,i));
		}
	}

	priority_queue<STATE> Q;

	//ますはstartから出発する
	for(int i = 0; i < G[start].size(); i++){
		if(G[start][i].min_cost > G[start][i].cost){
			G[start][i].min_cost = G[start][i].cost;
			G[start][i].min_change_num = 0;
			Q.push(STATE(G[start][i].to,G[start][i].cost,0,G[start][i].line_id,G[start][i].in_line_index,start,i));
		} //最初は乗り換え回数が0なので、乗り換え回数の最小値更新は起こり得ない
	}

	int next_st,next_cost,next_change;

	while(!Q.empty()){

		if(Q.top().st_id == goal){
			printf("%d %d\n",Q.top().sum_cost,Q.top().change_num);
			return 0;
		}else if((Q.top().sum_cost > G[Q.top().pre_node][Q.top().pre_id].min_cost) ||
				(Q.top().sum_cost == G[Q.top().pre_node][Q.top().pre_id].min_cost && Q.top().change_num > G[Q.top().pre_node][Q.top().pre_id].min_change_num)){
			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().st_id].size(); i++){

				next_st = G[Q.top().st_id][i].to;
				next_cost = Q.top().sum_cost+G[Q.top().st_id][i].cost;
				next_change = Q.top().change_num;

				if(G[Q.top().st_id][i].line_id != Q.top().line_id || abs(G[Q.top().st_id][i].in_line_index-Q.top().in_line_index) != 1){ //★★同じ路線内での乗り換えに注意★★
					next_cost += T;
					next_change++;
				}

				if(G[Q.top().st_id][i].min_cost > next_cost){ //あるエッジ上を動く時、過去最少コストなら遷移させる
					G[Q.top().st_id][i].min_cost = next_cost;
					G[Q.top().st_id][i].min_change_num = next_change;
					Q.push(STATE(next_st,next_cost,next_change,G[Q.top().st_id][i].line_id,G[Q.top().st_id][i].in_line_index,Q.top().st_id,i));
				}else if(G[Q.top().st_id][i].min_cost == next_cost && G[Q.top().st_id][i].min_change_num > next_change){
					G[Q.top().st_id][i].min_change_num = next_change;
					Q.push(STATE(next_st,next_cost,next_change,G[Q.top().st_id][i].line_id,G[Q.top().st_id][i].in_line_index,Q.top().st_id,i));
				}
			}

			Q.pop();
		}
	}

	printf("-1\n");

	return 0;
}