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 <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

constexpr int MAX_V = 100000;
constexpr int MAX_N = 50000;

typedef pair<int, int> D; // dist, change
typedef tuple<D, int, int> P; // D, rail, pos

vector<int> p[MAX_N];
vector<int> t[MAX_N];
vector<D> dist[MAX_N];

bool visited[MAX_V];
set<pair<int, int>> S[MAX_V];
unordered_map<string, int> converter;

inline int input_station() {
	string station_name;
	cin >> station_name;

	if(!converter.count(station_name)) {
		converter.insert({station_name, converter.size()});
	}

	return converter[station_name];
}

string dijkstra(int s, int g, int T) {
	memset(visited, false, sizeof(visited));
	priority_queue<P, vector<P>, greater<P>> que;

	for(const auto &e : S[s]) {
		dist[e.first][e.second] = D(0, 0);
		que.push(make_tuple(D(0, 0), e.first, e.second));
	}

	while(!que.empty()) {
		D d;
		int r, q;
		tie(d, r, q) = que.top();
		que.pop();

		if(dist[r][q] < d) continue;

		const int v = p[r][q];

		if(v == g) return to_string(d.first) + " " + to_string(d.second);

		if(!visited[v]) {
			for(const auto &e : S[v]) {
				const D next_dist(d.first + T, d.second + 1);

				if(dist[e.first][e.second] > next_dist) {
					dist[e.first][e.second] = next_dist;
					que.push(make_tuple(next_dist, e.first, e.second));
				}
			}
		}

		visited[v] = true;

		if(0 < q) {
			const D next_dist(d.first + t[r][q - 1], d.second);

			if(dist[r][q - 1] > next_dist) {
				dist[r][q - 1] = next_dist;
				que.push(make_tuple(next_dist, r, q - 1));
			}
		}

		if(q < static_cast<int>(p[r].size()) - 1) {
			const D next_dist(d.first + t[r][q], d.second);

			if(dist[r][q + 1] > next_dist) {
				dist[r][q + 1] = next_dist;
				que.push(make_tuple(next_dist, r, q + 1));
			}
		}
	}

	return "-1";
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, T;
	cin >> N >> T;

	const int A = input_station();
	const int B = input_station();

	for(int i = 0; i < N; ++i) {
		int a;
		cin >> a;

		p[i].resize(a);
		t[i].resize(a - 1);
		dist[i].resize(a, D(INT_MAX, INT_MAX));

		for(int j = 0; j < a; ++j) {
			p[i][j] = input_station();
			S[p[i][j]].insert({i, j});
		}

		for(auto &e : t[i]) cin >> e;
	}

	cout << dijkstra(A, B, T) << endl;
}