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;

using pii = pair<int, int>;
constexpr int INF = 1e9;

struct edge {
    int to, cost, id;
};

using edges = vector<edge>;
using graph = vector<edges>;

struct state {
    int v, id;
    pii cost;
    bool operator<(state const& s) const {
        return cost > s.cost;
    }
};

int main() {
    int N, T;
    cin >> N >> T;
    map<string, int> id;
    string A, B;
    cin >> A >> B;
    id[A] = 0;
    id[B] = 1;
    graph g(1000001);
    int now = 0;
    for(int i=0; i<N; ++i) {
        int a;
        cin >> a;
        vector<int> idx(a);
        for(int j=0; j<a; ++j) {
            string s;
            cin >> s;
            if(id.count(s) == 0) {
                id[s] = id.size()-1;
            }
            idx[j] = id[s];
        }
        g.resize(id.size());
        for(int j=0; j<a-1; ++j) {
            int t;
            cin >> t;
            g[idx[j]].push_back(edge{idx[j+1], t, now});
            g[idx[j+1]].push_back(edge{idx[j], t, now});
            now++;
        }
        now++;
    }
    vector<pii> d(100001, make_pair(INF, INF));
    priority_queue<state> que;
    que.push(state{0, -1, make_pair(0, 0)});
    pii res = make_pair(INF, INF);
    while(!que.empty()) {
        state now = que.top();
        que.pop();
        if(now.id != -1 && d[now.id] < now.cost) {
            continue;
        }
        if(now.v == 1) {
            res = now.cost;
            break;
        }
        for(auto& e : g[now.v]) {
            int cost = e.cost;
            bool trans = false;
            if(now.id != -1 && abs(now.id - e.id) != 1) {
                cost += T;
                trans = true;
            }
            auto next = make_pair(now.cost.first + cost, now.cost.second + trans);
            if(d[e.id] > next) {
                d[e.id] = next;
                que.push(state{e.to, e.id, next});
            }
        }
    }

    if(res.first == INF) {
        cout << -1 << endl;
    } else {
        cout << res.first << ' ' << res.second << endl;
    }
}