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;
typedef long long ll;
typedef pair<ll, int> edge;
typedef pair<edge,int> state;

const ll INF = 1e9;

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

  int n,t;
  cin >> n >> t;

  map<string, vector<int> > id;
  int v = 0;
  string A,B;
  cin >> A >> B;

  vector<string> name;
  vector< vector<int> > c(n);

  for(int i=0;i<n;i++){
    int a; cin >> a;
    for(int j=0;j<a;j++){
      string tmp;
      cin >> tmp;
      id[tmp].push_back(v+j);
      name.push_back(tmp);
    }
    for(int j=0;j<a-1;j++){
      int tmp;
      cin >> tmp;
      c[i].push_back(tmp);
    }
    v += a;
  }

  vector< vector<edge> > g(v);
  v = 0;
  for(int i=0;i<n;i++){
    for(int j=0;j<(int)c[i].size();j++){
      g[v].push_back(edge(c[i][j],v+1));
      g[v+1].push_back(edge(c[i][j],v));
      v++;
    }
    v++;
  }

  priority_queue<state,vector<state>,greater<state> > q;
  vector<edge> d(v,edge(INF,INF));
  for(int u : id[A]){
    q.push(state(edge(0,0),u));
    d[u] = edge(0,0);
  }
  set<string> use;

  while(q.size()){
    state s = q.top(); q.pop();
    int u = s.second;
    edge cost = s.first;
    if(d[u] < cost)continue;

    for(edge nxt : g[u]){
      edge nxtc = edge(nxt.first + cost.first, cost.second);
      int nxtu = nxt.second;
      if(d[nxtu] > nxtc){
	d[nxtu] = nxtc;
	q.push(state(nxtc,nxtu));
      }
    }

    if(use.count(name[u])==0){
      use.insert(name[u]);
      edge nxtc = edge(cost.first + t, cost.second + 1);
      for(int nxtu : id[name[u]]){
	if(d[nxtu] > nxtc){
	  d[nxtu] = nxtc;
	  q.push(state(nxtc,nxtu));
	}
      }
    }
  }


  edge ans = edge(INF,INF);
  for(int u : id[B]){
    ans = min(ans, d[u]);
  }

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