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;
#define int long long
struct edge{
  int to,cost,rcost;
  edge(){}
  edge(int to,int cost,int rcost):to(to),cost(cost),rcost(rcost){}
};
signed main(){
  int n,t;
  cin>>n>>t;
  string a,b;
  cin>>a>>b;
  int c[n];
  vector<string> vs[n];
  vector<int> vi[n];
  for(int i=0;i<n;i++){
    cin>>c[i];
    vs[i].resize(c[i]);
    vi[i].resize(c[i]-1);
    for(int j=0;j<c[i];j++) cin>>vs[i][j];
    for(int j=0;j<c[i]-1;j++) cin>>vi[i][j];
  }
  int cnt=0;
  map<string,int> m;
  m[a]=cnt++;
  m[b]=cnt++;
  for(int i=0;i<n;i++)
    for(int j=0;j<c[i];j++)
      if(!m.count(vs[i][j]))
	m[vs[i][j]]=cnt++;
  int sum=0;
  for(int i=0;i<n;i++) sum+=c[i];
  vector<vector<edge> > G(cnt+sum);
  int tmp=cnt;
  for(int i=0;i<n;i++){
    for(int j=0;j<c[i];j++){
      G[m[vs[i][j]]].push_back(edge(tmp,t,0));
      G[tmp].push_back(edge(m[vs[i][j]],0,t));
      if(j<c[i]-1){
	G[tmp].push_back(edge(tmp+1,vi[i][j],vi[i][j]));
	G[tmp+1].push_back(edge(tmp,vi[i][j],vi[i][j]));
      }
      tmp++;
    }
  }
  assert(tmp==cnt+sum);
  int inf=1LL<<55LL;
  vector<int> dist(tmp,inf);
  typedef pair<int,int> P;
  priority_queue<P,vector<P>,greater<P> > q;
  dist[m[a]]=0;
  q.push(P(0,m[a]));
  while(!q.empty()){
    P p=q.top();q.pop();
    int d=p.first,v=p.second;
    if(dist[v]<d) continue;
    for(edge e:G[v]){
      if(dist[e.to]>dist[v]+e.cost){
	dist[e.to]=dist[v]+e.cost;
	q.push(P(dist[e.to],e.to));
      }
    }
  }
  if(dist[m[b]]==inf){
    cout<<-1<<endl;
    return 0;
  }
  vector<int> dist2(tmp,inf);
  dist2[m[b]]=0;
  q.push(P(0,m[b]));
  while(!q.empty()){
    P p=q.top();q.pop();
    int d=p.first,v=p.second;
    //cout<<d<<" "<<v<<endl;
    if(dist2[v]<d) continue;
    for(edge e:G[v]){
      //cout<<e.to<<" "<<e.rcost<<":"<<dist[e.to]<<" "<<dist[v]<<endl;
      if(dist[e.to]+e.rcost!=dist[v]) continue;
      //cout<<e.to<<":"<<dist2[e.to]<<" "<<dist2[v]+(0<=e.to&&e.to<cnt)<<endl;
      if(dist2[e.to]>dist2[v]+(0<=e.to&&e.to<cnt)){
	dist2[e.to]=dist2[v]+(0<=e.to&&e.to<cnt);
	q.push(P(dist2[e.to],e.to));
      }
    }
  }
  cout<<dist[m[b]]-t<<" "<<dist2[m[a]]-1<<endl;
  return 0;
}