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>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const ll INF = (1LL << 60);

class Dijkstra {
public:
  struct edge {
    ll v;
    pll dist;
  };

  struct state {
    ll v;
    pll cost;
    bool operator>(const state s) const { return cost > s.cost; }
  };

  ll N;
  vector< vector<edge> > E;

  Dijkstra(ll n): N(n), E(n) {}

  void add_directed_edge(ll u, ll v, pll d) {
    E[u].push_back((edge) { v, d });
  }

  vector<pll> shortest_path(ll S) {
    vector<pll> dp(E.size(), pll(INF, INF));
    priority_queue<state, vector<state>, greater<state>> q;
    q.push((state) { S, pll(0, 0) });
    while(!q.empty()) {
      ll v = q.top().v;
      pll cost = q.top().cost;
      q.pop();
      if(dp[v] <= cost) continue;
      dp[v] = cost;
      REP(i, 0, E[v].size()) {
        ll nv = E[v][i].v;
        pll ncost = pll(cost.first + E[v][i].dist.first, cost.second + E[v][i].dist.second);
        if(dp[nv] > ncost) q.push((state) { nv, ncost });
      }
    }
    return dp;
  }
};

int main(void) {
  ll N, Time;
  cin >> N >> Time;
  string A, B;
  cin >> A >> B;
  vector<vector<string>> S(N);
  vector<vector<ll>> T(N);
  REP(i, 0, N) {
    ll a; cin >> a;
    REP(j, 0, a) {
      string s; cin >> s;
      S[i].push_back(s);
    }
    REP(j, 0, a - 1) {
      ll t; cin >> t;
      T[i].push_back(t);
    }
  }

  vector<string> vec;
  vec.push_back(A);
  vec.push_back(B);
  REP(i, 0, N) REP(j, 0, S[i].size()) vec.push_back(S[i][j]);
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());

  vector<pair<ll, string>> idx;
  REP(i, 0, N) REP(j, 0, S[i].size()) idx.push_back(pair<ll, string>(i * 1000000000 + j, S[i][j]));
  REP(i, 0, vec.size()) idx.push_back(pair<ll, string>(-1, vec[i]));
  sort(idx.begin(), idx.end());

  Dijkstra dijk(idx.size());
  ll s = lower_bound(idx.begin(), idx.end(), pair<ll, string>(-1, A)) - idx.begin();
  ll g = lower_bound(idx.begin(), idx.end(), pair<ll, string>(-1, B)) - idx.begin();
  REP(i, 0, N) {
    REP(j, 0, S[i].size() - 1) {
      ll p = lower_bound(idx.begin(), idx.end(), pair<ll, string>(i * 1000000000 + j, S[i][j])) - idx.begin();
      ll q = lower_bound(idx.begin(), idx.end(), pair<ll, string>(i * 1000000000 + j + 1, S[i][j + 1])) - idx.begin();
      dijk.add_directed_edge(p, q, pll(T[i][j], 0));
      dijk.add_directed_edge(q, p, pll(T[i][j], 0));
    }
  }
  REP(i, 0, N) {
    REP(j, 0, S[i].size()) {
      ll p = lower_bound(idx.begin(), idx.end(), pair<ll, string>(i * 1000000000 + j, S[i][j])) - idx.begin();
      ll q = lower_bound(idx.begin(), idx.end(), pair<ll, string>(-1, S[i][j])) - idx.begin();
      if(q != g) {
        dijk.add_directed_edge(p, q, pll(Time, 1));
        dijk.add_directed_edge(q, p, pll(0, 0));
      } else {
        dijk.add_directed_edge(p, q, pll(0, 0));
        dijk.add_directed_edge(q, p, pll(0, 0));
      }
    }
  }

  pll ans = dijk.shortest_path(s)[g];
  if(ans == pll(INF, INF)) cout << -1 << endl;
  else cout << ans.first << " " << ans.second << endl;
}