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 <cstdio>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#define int long long int // !!!!!!!!
using namespace std;

map< pair< string, pair<int, int> >, int> hs;
map< string, int > hs_station;

int N, T;
string A, B;

struct Edge {
  int to, cost, trans;
};

struct Elem {
  int pos, cost, trans;
  bool operator<(const Elem &e) const {
    if(cost != e.cost) return cost > e.cost;
    return trans > e.trans;
  }
};

vector< Edge > G[200010];
pair<int, int> dist[200010];
const pair<int, int> INF = make_pair(1LL << 50, 1LL << 50);

signed main() {
  cin >> N >> T >> A >> B;

  int sum = 0;
  vector< vector<string> > stations(N);
  vector< vector<int>    > times(N);
  for(int i=0; i<N; i++) {
    int station; cin >> station;
    sum += station;
    stations[i].resize(station);
    times[i].resize(station - 1);
    
    for(int k=0; k<station; k++) {
      cin >> stations[i][k];
      hs[ make_pair(stations[i][k], make_pair(i, k)) ] = 0;
      hs_station[ stations[i][k] ] = 0;
    }

    for(int k=0; k<station - 1; k++) {
      cin >> times[i][k];
    }
  }

  int id = 0, offs = 0;

  // id set
  set<int> start_S, end_S;
  for(auto &x : hs) {
    x.second = id++;

    if(x.first.first == A) {
      start_S.insert(x.second);
    }
    if(x.first.first == B) {
      end_S.insert(x.second);
    }
  }
  offs = id;

  id = 0;
  for(auto &x : hs_station) {
    x.second = offs + (id++);
  }

  // transfer vertex: id = sum
  for(int i=0; i<N; i++) {
    int sz = stations[i].size();

    // station <-> station
    for(int k=0; k<sz-1; k++) {
      // get hash (key: station and index)
      int u = hs[ make_pair(stations[i][k], make_pair(i, k)) ];
      int v = hs[ make_pair(stations[i][k+1], make_pair(i, k+1)) ];
      int cost = times[i][k];

      // printf("u: station = %s, id = %d\n", stations[i][k].c_str(), i+1);
      // printf("v: station = %s, id = %d\n", stations[i][k+1].c_str(), i+1);
      // printf("cost = %d\n", cost);

      G[u].push_back(Edge{v, cost, 0});
      G[v].push_back(Edge{u, cost, 0});
    }

    // station <-> transfer
    for(int k=0; k<sz; k++) {
      int u = hs[ make_pair(stations[i][k], make_pair(i, k)) ];
      int v = hs_station[ stations[i][k] ];
      G[u].push_back(Edge{v, 0, 0});
      G[v].push_back(Edge{u, T, 1});
    }
  }

  fill(dist, dist+200010, INF);

  // pos, cost, trans
  priority_queue<Elem> que;
  for(auto x : start_S) {
    dist[x] = make_pair(0, 0);
    que.push(Elem{x, 0, 0});
  }

  while(que.size()) {
    Elem cur = que.top(); que.pop();

    for(auto e : G[cur.pos]) {
      int to = e.to;
      int n_cost = cur.cost + e.cost;
      int n_trans = cur.trans + e.trans;

      // printf("cur = %d, to = %d, n_cost = %d, n_trans = %d\n", cur.pos, to, n_cost, n_trans);

      if(dist[to] > make_pair(n_cost, n_trans)) {
        dist[to] = make_pair(n_cost, n_trans);
        que.push(Elem{to, n_cost, n_trans});
      }
    }
  }
  
  pair<int, int> ans = INF;
  for(auto x : end_S) {
    ans = min(ans, dist[x]);
  }

  if(ans == INF) cout << -1 << endl;
  else cout << ans.first << " " << ans.second << endl;
  return 0;
}