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 i64 = int64_t;

const i64 MOD = 1e9 + 7;


signed main(){
    int n, t;
    string as, bs;
    cin >> n >> t >> as >> bs;
    int station_cnt = 0;

    // ros, pos
    unordered_map<string, int> tai;

    vector<int> road_num(n);
    vector<vector<int>> station(n);
    vector<vector<int>> dist(n);
    // range[ros][ros_pos][0,1]
    vector<vector<vector<pair<int,int>>>> range(n);
    for(int i = 0; i < n; ++i){
        cin >> road_num[i];
        station[i].resize(road_num[i]);
        range[i].resize(road_num[i], vector<pair<int,int>>(2, make_pair(MOD,MOD)));
        for(int j = 0; j < road_num[i]; ++j){
            string str;
            cin >> str;
            if(tai.find(str) == tai.end())
                tai[str] = station_cnt++;
            station[i][j] = tai[str];
        }
        dist[i].resize(road_num[i] - 1);
        for(auto& x : dist[i])
            cin >> x;
    }
    vector<vector<pair<int,int>>> s(station_cnt);

    int start_point = tai[as];
    int end_point = tai[bs];

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < road_num[i]; ++j)
            s[station[i][j]].emplace_back(i, j);
    }
    priority_queue<tuple<int,int,int,int,int>, vector<tuple<int,int,int,int,int>>, greater<tuple<int,int,int,int,int>>> que;
    for(auto& p : s[start_point]){
        range[p.first][p.second][0] = make_pair(0, 0);
        range[p.first][p.second][1] = make_pair(0, 0);
        que.emplace(0, 0, p.first, p.second, 0);
        que.emplace(0, 0, p.first, p.second, 1);
    }
    vector<int> b(station_cnt, 0);

    // 0: back
    // 1: forward
    while(!que.empty()){
        int d, nor, ros, ros_pos, rot;
        tie(d, nor, ros, ros_pos, rot) = que.top();
        int pos = station[ros][ros_pos];
        que.pop();
        if(range[ros][ros_pos][rot] != make_pair(d, nor))
            continue;

        if(!rot && ros_pos != 0){
            auto nex = make_pair(d + dist[ros][ros_pos - 1], nor);
            if(range[ros][ros_pos - 1][rot] > nex){
                range[ros][ros_pos - 1][rot] = nex;
                que.emplace(nex.first, nex.second, ros, ros_pos - 1, rot);
            }
        }
        if(rot && ros_pos != road_num[ros] - 1){
            auto nex = make_pair(d + dist[ros][ros_pos], nor);
            if(range[ros][ros_pos + 1][rot] > nex){
                range[ros][ros_pos + 1][rot] = nex;
                que.emplace(nex.first, nex.second, ros, ros_pos + 1, rot);
            }
        }
        auto nex = make_pair(d + t, nor + 1);
        if(b[pos])
            continue;
        b[pos] = 1;
        for(auto& p : s[pos]){
            if(range[p.first][p.second][0] > nex){
                range[p.first][p.second][0] = nex;
                que.emplace(nex.first, nex.second, p.first, p.second, 0);
            }
            if(range[p.first][p.second][1] > nex){
                range[p.first][p.second][1] = nex;
                que.emplace(nex.first, nex.second, p.first, p.second, 1);
            }
        }
    }

    pair<int,int> ret = make_pair(MOD, MOD);
    for(auto& p : s[end_point]){
        ret = min(ret, range[p.first][p.second][0]);
        ret = min(ret, range[p.first][p.second][1]);
    }

    if(ret.first == MOD)
        cout << -1 << endl;
    else
        cout << ret.first << " " << ret.second << endl;

}