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:
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

// 時間、乗り換え回数
const pair<int, int> PINF(INF, INF);
pair<int, int> rec[200010];

int N, T, pa, pb;
string A, B;
map<string, int> comp;
vector< tuple<int, int, int> > G[200010];

struct Elem {
    int pos, tm, tf;
    Elem() {}
    Elem(int a, int b, int c) : pos(a), tm(b), tf(c) {}
    bool operator<(const Elem &e) const {
        if(tm != e.tm) return tm > e.tm;
        return tf > e.tf;
    }
};
 
signed main() {
    cin >> N >> T;
    cin >> A >> B;
    comp[A]++; comp[B]++;

    vector< vector<string> > stations(N);
    vector< vector<int> > times(N);
    int L = 0;
    for(int i=0; i<N; i++) {
        int M; cin >> M;
        L += M;
        for(int k=0; k<M; k++) {
            string s; cin >> s;
            comp[s]++;
            stations[i].emplace_back(s);
        }
        for(int k=0; k<M-1; k++) {
            int v; cin >> v;
            times[i].emplace_back(v);
        }
    }

    int id = 0; for(auto &e : comp) e.second = id++;
    pa = comp[A], pb = comp[B];

    int S = id;
    vector< vector<int> > info(S);

    int cnt = 0;
    for(int i=0; i<N; i++) {
        int M = stations[i].size();
        for(int k=0; k<M-1; k++) {
            int u = cnt + k;
            int v = cnt + k + 1;
            int c = times[i][k];

            // direct
            G[u].emplace_back(v, c, 0);
            G[v].emplace_back(u, c, 0);
            // fprintf(stderr, "direct: (%lld, %lld)\n", u, v);
        }

        for(int k=0; k<M; k++) {
            int u = cnt + k;
            int v = L + comp[ stations[i][k] ];
            info[ comp[ stations[i][k] ] ].emplace_back(u);
            
            // fprintf(stderr, "transfer: (%lld, %lld)\n", u, v);
            G[u].emplace_back(v, 0, 0);
            G[v].emplace_back(u, T, 1);
        }
        cnt += M;
    }

    // L は元の入力で与えられた駅数、S は乗り換え用駅数
    fill(rec, rec + L + S, PINF);
    priority_queue<Elem> que;
    for(auto e : info[pa]) {
        rec[e] = make_pair(0, 0);
        que.emplace(e, 0, 0);
    }

    while(que.size()) {
        auto cur = que.top(); que.pop();
        auto p = make_pair(cur.tm, cur.tf);
        if(rec[cur.pos] < p) continue;

        for(auto e : G[cur.pos]) {
            int to, tm, tf; tie(to, tm, tf) = e;
            int ntm = cur.tm + tm;
            int ntf = cur.tf + tf;
            if(rec[to] > make_pair(ntm, ntf)) {
                rec[to] = make_pair(ntm, ntf);
                que.emplace(to, ntm, ntf);
            }
        }
    }

    pair<int, int> ans = PINF;
    for(auto e : info[pb]) {
        chmin(ans, rec[e]);
    }
    if(ans == PINF) puts("-1");
    else printf("%lld %lld\n", ans.first, ans.second);
    return 0;
}