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;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct edge {
  int to, et, tr;
  edge(){}
  edge(int to, int et, int tr):to(to), et(et), tr(tr){}
};

int n_railway;
int t_transfer;
string start_st, goal_st;
vector<vector<string> > railway_info_st;
vector<vector<int> > railway_info_t;
int n_node;
map<string, int> conv;
vector<vector<edge> > graph;

using PP = pair<Pi, int>;
Pi dijkstra(int s, int t) {
  vector<Pi> mincost(n_node, Pi(inf, inf));
  priority_queue<PP, vector<PP>, greater<PP> > que;
  mincost[s] = Pi(0, 0);
  que.emplace(Pi(0, 0), s);
  while(!que.empty()) {
    PP p = que.top(); que.pop();
    int v = p.second;
    if(v == t) return mincost[v];
    if(mincost[v] < p.first) continue;
    for(edge e : graph[v]) {
      Pi cost = Pi(mincost[v].first+e.et, mincost[v].second+e.tr);
      if(cost < mincost[e.to]) {
	mincost[e.to] = cost;
	que.emplace(cost, e.to);
      }
    }
  }
  return Pi(inf, inf);
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> n_railway >> t_transfer;
  cin >> start_st >> goal_st;

  railway_info_st.resize(n_railway);
  railway_info_t.resize(n_railway);

  for(int i = 0; i < n_railway; ++i) {
    int n_st; cin >> n_st;

    n_node += n_st;

    railway_info_st[i].resize(n_st);
    for(int j = 0; j < n_st; ++j) cin >> railway_info_st[i][j];

    railway_info_t[i].resize(n_st);
    for(int j = 0; j < n_st-1; ++j) cin >> railway_info_t[i][j];
  }

  graph.resize(n_node);

  int sz = 0;
  for(int i = 0; i < n_railway; ++i) {
    for(int j = 0; j < (int)railway_info_st[i].size(); ++j) {
      int u = sz++;
      if(!conv.count(railway_info_st[i][j])) {
	conv[railway_info_st[i][j]] = n_node++;
	graph.emplace_back();
      }
      int x = conv[railway_info_st[i][j]];
      graph[u].emplace_back(x, t_transfer, 1);
      graph[x].emplace_back(u, 0, 0);

      if(j == (int)railway_info_st[i].size()-1) continue;

      int v = sz;
      int t = railway_info_t[i][j];
      graph[u].emplace_back(v, t, 0);
      graph[v].emplace_back(u, t, 0);
    }
  }

  Pi ans = dijkstra(conv[start_st], conv[goal_st]);
  if(ans.first == inf) cout << -1 << endl;
  else cout << ans.first-t_transfer << " " << ans.second-1 << endl;

  return 0;
}