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 <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <memory>
#include <cstring>
#include <cassert>
#include <numeric>
#include <sstream>
#include <complex>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#define REP2(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(S) (S).begin(), (S).end()

template <typename T, typename E>
ostream &operator<<(std::ostream &os, const std::pair<T, E> &p){
  return os << "(" << p.first << ", " << p.second << ")";
}

typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  typedef pair<int, int>    PI;
  typedef pair<PI, PI>      PP;

  map<PI, string> name;
  map<string, vector<PI> > pos;
  map<PI, vector<PI> > G;
  map<PI, PI> cost;
  map<string, int> id;
  priority_queue<PP, vector<PP>, greater<PP> > que;

  int N, T;
  string A, B;
  cin >> N >> T >> A >> B;
  
  REP(i, N){
    int a;
    cin >> a;
    vector<string> stations(a);
    vector<int> distance(a - 1);
    REP(j, a){
      cin >> stations[j];
      pos[stations[j]].push_back(PI(i, j));
      name[PI(i, j)] = stations[j];

      if (stations[j] == A){
        cost[PI(i, j)] = PI(0, 0);
        que.push(PP(PI(0, 0), PI(i, j)));
      }

      if (id.find(stations[j]) == id.end()){
        int size = id.size();
        id[stations[j]] = size;
        name[PI(size, -1)] = stations[j];
      }
    }
    
    REP(j, a - 1){
      cin >> distance[j];
      G[PI(i, j)].push_back(PI(j + 1, distance[j]));
      G[PI(i, j + 1)].push_back(PI(j, distance[j]));
    }
  }
  
  while (!que.empty()){
    PI ps = que.top().second;
    PI pi = que.top().first;
    que.pop();

    if (name[ps] == B){
      cout << pi.first << " " << pi.second << endl;
      exit(EXIT_SUCCESS);
    }

    if (cost[ps] < pi) continue;
    
    if (ps.second == -1){       // norikae
      for (PI next : pos[name[ps]]){
        auto iter = cost.find(next);
        if (iter == cost.end() || iter->second > pi){
          cost[next] = pi;
          que.push(PP(pi, next));
        }
      }
    } else {
      PI nps(id[name[ps]], -1);
      PI npi(pi.first + T, pi.second + 1);
      auto iter = cost.find(nps);
      if (iter == cost.end() || iter->second > npi){
        cost[nps] = npi;
        que.push(PP(npi, nps));
      }

      for (const PI &e : G[ps]){
        PI nps(ps.first, e.first);
        PI npi(pi.first + e.second, pi.second);
        auto iter = cost.find(nps);
        if (iter == cost.end() || iter->second > npi){
          cost[nps] = npi;
          que.push(PP(npi, nps));
        }
      }
    }
  }
  cout << -1 << endl;
  
  return 0;
}