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>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
//const ll mod = 1000000007;
typedef pair<string, ll> sl;
typedef pair<l_l, sl> llsl;
map<sl, vector<llsl>> paths;
map<sl, l_l> dist;
string A, B;
ll N, T;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> T >> A >> B;
    for(int j = 1; j <= N; j++) {
        ll a;
        cin >> a;
        vector<string> S(a);
        vector<ll> t(a - 1);
        for(int i = 0; i < a; i++) {
            cin >> S[i];
            paths[{S[i], 0}].push_back({{0, 0}, {S[i], j + 1e9 * i}});
            paths[{S[i], j + 1e9 * i}].push_back({{T, 1}, {S[i], 0}});
        }
        for(int i = 0; i < a - 1; i++) cin >> t[i];
        for(int i = 0; i < a - 1; i++) {
            paths[{S[i], j + 1e9 * i}].push_back({{t[i], 0}, {S[i+1], j + 1e9 * (i+1)}});
            paths[{S[i+1], j + 1e9 * (i+1)}].push_back({{t[i], 0}, {S[i], j+1e9*i}});
        }
    }
    priority_queue<llsl, vector<llsl>, greater<llsl>> que;
    dist[{A, 0}] = {0, 0};
    que.push({{0, 0}, {A, 0}});
    while(!que.empty()) {
        auto tmp = que.top();
        que.pop();
        sl now = tmp.second;
        l_l nowcost = tmp.first;
        for(auto tmp : paths[now]) {
            sl to = tmp.second;
            l_l newcost = tmp.first;
            newcost.first += nowcost.first;
            newcost.second += nowcost.second;
            if(dist.count(to) == 0 or chmin(dist[to], newcost)) {
                dist[to] = newcost;
                que.push({newcost, to});
            }
        }
    }
    if(dist.count({B, 0}) == 0) {
        cout << -1 << endl;
        return 0;
    }
    l_l ans = dist[{B, 0}];
    cout << ans.first - T << " " << ans.second - 1 << endl;
    return 0;
}