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<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl
#define F first
#define S second
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int n, t;
string a, b;
map<string, int> id;
vi rail[50000], cost[50000];
vector<pi> pos[100000];
bool trans[100000]; //respect fra2

inline int get(const string &s){
	if(id.count(s)) return id[s];
	int n = id.size();
	return id[s] = n;
}
int main(){
	cin >> n >> t >> a >> b;
	int st = get(a), gl = get(b);
	rep(i, n){
		int k, l;
		cin >> k;
		rep(j, k){
			string s;
			cin >> s;
			l = get(s);
			rail[i].pb(l);
			pos[l].pb(mp(i, j));
		}
		rep(j, k - 1){
			cin >> l;
			cost[i].pb(l);
		}
	}
	set<pi> s;
	priority_queue<pair<pi, pi> > q;
	rep(i, pos[st].size()) q.push(mp(mp(0, 0), pos[st][i]));
	while(!q.empty()){
		pi cur = q.top().S, co = q.top().F;
		int cid = rail[cur.F][cur.S]; q.pop();
		if(s.count(cur)) continue;
		s.insert(cur);
		
		if(cid == gl){
			cout << -co.F << " " << -co.S << endl;
			return 0;
		}
		if(!trans[cid]){
			trans[cid] = 1;
			rep(i, pos[cid].size()) rep(d, 2){
				pi nxt = pos[cid][i], nco = co;
				nxt.S += d ? 1 : -1;
				if(nxt.S < 0 || nxt.S >= rail[nxt.F].size() || s.count(nxt)) continue;
				if(pos[cid][i] == cur) continue;
				nco.S--;
				nco.F -= t + cost[nxt.F][nxt.S - d];
				q.push(mp(nco, nxt));
			}
		}
		rep(d, 2){
			pi nxt = cur, nco = co;
			nxt.S += d ? 1 : -1;
			if(nxt.S < 0 || nxt.S >= rail[nxt.F].size() || s.count(nxt)) continue;
			nco.F -= cost[nxt.F][nxt.S - d];
			q.push(mp(nco, nxt));
		}
	}
	cout << -1 << endl;
	return 0;
}