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;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

vector<pair<int,PII>> G[200010];
const int BASE = 100000;
const int INF = 2e9;

void Dijkstra(vector<PII>& d, int s){
  using Type = pair<PII,int>;
  priority_queue<Type, vector<Type>, greater<Type> > pq;
  fill(d.begin(), d.end(), MP(INF,INF));
  d[s] = MP(0,0);
  pq.push(Type(MP(0,0),s));

  while(!pq.empty()){
	Type pii = pq.top(); pq.pop();
	int v = pii.second;
	if(d[v] < pii.first) continue;
	for(unsigned int i=0;i<G[v].size();++i){
	  const PII& cost = G[v][i].SS;
	  int to = G[v][i].FF;
	  PII nxt(pii.FF.FF + cost.FF, pii.FF.SS + cost.SS);
	  if(d[to] > nxt){
		d[to] = nxt;
		pq.push(MP(d[to], to));
	  }
	}
  }
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int gid = 0;
  unordered_map<string,int> id;

  int N, T; cin >> N >> T;
  string A, B; cin >> A >> B;
  id[A] = gid++;
  id[B] = gid++;
  int tot = 0;
  REP(i,N){
	int m; cin >> m;
	VI xs(m), ts(m-1);
	REP(i,m){
	  string s; cin >> s;
	  if(!id.count(s)) id[s] = gid++;
	  xs[i] = id[s];
	}
	REP(i,m-1) cin >> ts[i];
	
	REP(i,m-1){
	  G[tot+i].PB(MP(tot+i+1, MP(ts[i], 0)));
	  G[tot+i+1].PB(MP(tot+i, MP(ts[i], 0)));
	}
	REP(i,m){
	  G[tot+i].PB(MP(xs[i]+BASE, MP(T, 1)));
	  G[xs[i]+BASE].PB(MP(tot+i, MP(0, 0)));
	}
	tot += m;
  }
  
  vector<PII> d(200010);
  Dijkstra(d, id[A]+BASE);
  PII ans = d[id[B]+BASE];
  if(ans.FF == INF)
	cout << -1 << endl;
  else
	cout << ans.FF-T << " " << ans.SS-1 << endl;

  return 0;
}