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 <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<b?(a=b,1):0)
#define chmin(a,b) (a>b?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

int num;
map<string,int> mp;

int get(const string &s) {
  if (mp.count(s) == 0) mp[s] = num++;
  return mp[s];
}

int t[100000];
vector<int> v[100000];
vector<pii> g[100000];

void add(int i, int j, int d) {
  g[i].push_back(pii(j,d));
  g[j].push_back(pii(i,d));
}

struct P {
  int now, dist, count;
  P(int now, int dist, int count) :
    now(now),dist(dist),count(count) {}
  bool operator<(const P&b) const {
    return dist != b.dist ? dist > b.dist : count > b.count;
  }
};

pii dist[100000];
bool seen[100000];

int main() {
  int n,T;
  cin >> n >> T;
  string A,B;
  cin >> A >> B;
  int a = get(A);
  int b = get(B);
  int cnt = 0;
  map<pii,int> idmap;
  REP(i,n) {
    int k; cin >> k;
    REP(j,k) {
      string s;
      cin >> s;
      t[cnt] = get(s);
      v[get(s)].push_back(cnt);
      idmap[pii(i,j)] = cnt++;
    }
    REP(j,k-1) {
      int d; cin >> d;
      add(idmap[pii(i,j)], idmap[pii(i,j+1)], d);
    }
  }
  priority_queue<P> Q;
  REP(i,cnt) dist[i] = pii(INT_MAX, INT_MAX);
  FOR(it, v[a]) {
    Q.push(P(*it, 0, 0));
    dist[*it] = pii(0,0);
  }
  while(!Q.empty()) {
    P p = Q.top(); Q.pop();
    // cout << p.now << " " << p.dist  << " " << p.count << endl;
    pii pi = pii(p.dist, p.count);
    if (dist[p.now] < pi) continue;
    if (!seen[t[p.now]]) {
      seen[t[p.now]] = 1;
      FOR(it, v[t[p.now]]) {
        pii nxt = pii(p.dist+T,p.count+1);
        if (dist[*it] > nxt) {
          dist[*it] = nxt;
          Q.push(P(*it,nxt.first,nxt.second));
        }
      }
    }
    FOR(it, g[p.now]) {
      pii nxt = pii(p.dist+it->second, p.count);
      if (dist[it->first] > nxt) {
        dist[it->first] = nxt;
        Q.push(P(it->first, nxt.first, nxt.second));
      }
    }
  }
  pii ans(INT_MAX,INT_MAX);
  FOR(it, v[b]) {
    ans = min(ans, dist[*it]);
  }
  if (ans.first == INT_MAX) cout << -1 << endl;
  else cout << ans.first << " " << ans.second << endl;
}