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 <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 int long long int

template<typename Weight>
struct edge{
    size_t src, dst;
    Weight cost;

    edge() = default;
    edge(size_t src, size_t dst, Weight const& cost): src(src), dst(dst), cost(cost){}

    bool operator <(edge const &other) const{
        if(cost != other.cost) return cost < other.cost;
        if(src != other.src) return src > other.src;
        return dst < other.dst;
    }
};

template<typename Weight>
struct graph: std::vector<std::vector<edge<Weight>>>{
    graph(size_t n): std::vector<std::vector<edge<Weight>>>(n){}

    void connect_to(size_t src, size_t dst, Weight const& cost){
        (*this)[src].emplace_back(src, dst, cost);
    }

    void connect_with(size_t src, size_t dst, Weight const& cost){
        connect_to(src, dst, cost);
        connect_to(dst, src, cost);
    }
};

template<typename Weight>
std::vector<Weight> shortest(graph<Weight> const &g, size_t s = 0, Weight inf = numeric_limits<Weight>::max(), Weight ei = Weight()){
    // based on Dijkstra algorithm
    size_t n = g.size();
    std::vector<Weight> res(n, inf);
    using P = std::pair<Weight, size_t>;
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    res[s] = ei;
    pq.emplace(res[s], s);

    while(!pq.empty()){
        Weight cur_cost;
        size_t cur_node;
        std::tie(cur_cost, cur_node) = pq.top();
        pq.pop();
        if(res[cur_node] < cur_cost) continue;
        for(auto const& e: g[cur_node]){
            Weight next_cost = cur_cost+ e.cost;
            size_t next_node = e.dst;
            if(res[next_node] > next_cost){
                res[next_node] = next_cost;
                pq.emplace(next_cost, next_node);
            }
        }
    }

    return res;
}

template<typename T, typename U>
struct mypair: pair<T, U>{
    mypair operator +(mypair const &other) const{
         mypair ret;
         ret.first = (*this).first + other.first;
         ret.second = (*this).second + other.second;
         return ret;
    }
};


signed main(){

    int N, T; cin >> N >> T;
    int n = N;
    int cnt = 0;
    string A, B; cin >> A >> B;
    vector<vector<string> > s(n);
    vector<vector<int> > t(n);
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        cnt += a;
        for(int j = 0; j < a; j++){
            string str; cin >> str;
            s[i].emplace_back(str);
        }
        
        for(int j = 0; j < a - 1; j++){
            int val; cin >> val;
            t[i].emplace_back(val);
        }
    }


    map<string, int> to_home;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < (int)s[i].size(); j++){
            if(to_home.find(s[i][j]) == to_home.end()){
                to_home[s[i][j]] = cnt;
                cnt++;
            }
        }
    }
    

    graph<mypair<int, int>> g(cnt);
    cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < (int)s[i].size(); j++){
            // 改札を抜ける
            string name = s[i][j];
            int src = cnt;
            int home = to_home[name];
            mypair<int, int> add;
            add.first = T;
            add.second = 1;
            g.connect_to(src, home, add);
            add.first = 0;
            add.second = 0;
            g.connect_to(home, src, add);


            if(j != (int)s[i].size() - 1){
                int dst = cnt + 1;
                add.first = t[i][j];
                add.second = 0;
                g.connect_with(src, dst, add);
            }

            cnt++;
        }
    }

    mypair<int, int> e;
    e.first = 0;
    e.second = 0;
    mypair<int, int> inf;
    inf.first = 1000000000007;
    inf.second = inf.first;
    
    auto result = shortest(g, to_home[A], inf, e);
    if(result[to_home[B]] == inf) cout << -1 << endl;
    else cout << result[to_home[B]].first - T << " " << result[to_home[B]].second -1 << endl;

    return 0;
}