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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
struct Line {
	int from;
	int to;
	int id;
	long long int cost;
};
struct aa {
	Line l;
	pair<long long int,int> time;
};
class Compare {
public:
	//aa?????????????????¶
	bool operator()(const aa&l, const aa&r) {
		return l.time> r.time;
	}
};
map<string, int>mp;
vector<pair<long long int,int>>memo;
int main() {
	int N;long long int  T; cin >> N >> T;
	memo = vector<pair<long long int, int>>(100000, make_pair(1e18,0));
	vector<vector<Line>>ls(300000);
	string Start, Goal; cin >> Start >> Goal;
	mp[Start] = 0;
	mp[Goal] = 1;
	int num = 2;
	int id = 0;
	for (int i = 0; i < N; ++i) {
		int a; cin >> a;
		vector<int>stas;
		for (int j = 0; j < a; ++j) {
			string st; cin >> st;
			if (mp.find(st) == mp.end()) {
				mp[st] = num;
				num++;
			}
			stas.push_back(mp[st]);

		}
		for (int j = 0; j < a - 1; ++j) {
			int a; cin >> a;
			ls[stas[j]].push_back(Line{ stas[j],stas[j + 1],id,a });
			ls[stas[j+1]].push_back(Line{ stas[j+1],stas[j],id,a });
			id++; 
		}
		id++;
	}
	priority_queue<aa, vector<aa>, Compare>que;

	que.push(aa{ Line{-1,0,-100,0},make_pair(-T,-1) });
	long long int ans = -1;
	int change = -1;
	while (!que.empty()) {
		aa atop(que.top());
		que.pop();
		const int nowid = atop.l.id;
		const int nowtime = atop.time.first;
		const int nowchange = atop.time.second;
		const int now = atop.l.to;
		if (now == 1) {
			ans = nowtime;
			change = nowchange;
			break;
		}
		for (auto l : ls[now]) {
			const bool sameid = abs(l.id - nowid)<=1;
			const long long int nexttime = sameid ? nowtime + l.cost : nowtime + l.cost + T;
			const int nextchange = sameid ? nowchange : nowchange + 1;
			const auto nextp = make_pair(nexttime, nextchange);
			if (nextp < memo[l.id]) {
				memo[l.id] = nextp;
				que.push(aa{ l,nextp });
			}
		}

	}
	if (ans == -1) {
		cout << -1 << endl;
	}
	else {
		cout << ans << " " << change << endl;
	}
	return 0;
}