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>
#define INF (1e9)
#define N 100005
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> P2;

int n, T;
string A, B;
vector<P> G[N];
map<string,vector<int> > memo;
string s[N];
int ti[N];
string itos[N];

set<string> used;
priority_queue<P2,vector<P2>,greater<P2> > q;
P d[N];

P dijkstra(){
  
  for(int i=0;i<n;i++) d[i]=P(INF,INF);
  
  for(int i=0;i<n;i++)

    if(A==itos[i]){
      
      d[i]=P(0,0);

      q.push(P2(P(0,0),i));      
    }
    
  while(!q.empty()){

    P2 t=q.top(); q.pop();

    int cost1=t.first.first;
    int cost2=t.first.second;
    int node=t.second;

    if(itos[node]==B) return P(cost1,cost2);
    
    if(d[node]<P(cost1,cost2)) continue;
    
    if(!used.count(itos[node])){

      used.insert(itos[node]);
      
      for(int i=0;i<memo[itos[node]].size();i++){

	int next=memo[itos[node]][i];

	if(d[next]>P(cost1+T,cost2+1)){
	  d[next]=P(cost1+T,cost2+1);
	  q.push(P2(P(cost1+T,cost2+1),next));
	}
	
      }
      
    }

    for(int i=0;i<G[node].size();i++){

      int next=G[node][i].first;
      int c=G[node][i].second;
      
      if(d[next]>P(cost1+c,cost2)){
	d[next]=P(cost1+c,cost2);
	q.push(P2(P(cost1+c,cost2),next));
      }
      
    }
    
  }

  return P(-1,-1);
}

int main(){
  
  cin>>n>>T;
  cin>>A>>B;

  int cnt=0;
  
  for(int i=0;i<n;i++){
    
    int a;
    scanf("%d",&a);

    for(int j=0;j<a;j++) cin>>s[j];
    
    for(int j=0;j<a-1;j++) scanf("%d",&ti[j]);

    for(int j=0;j<a;j++){

      if(j!=a-1){
	G[cnt].push_back(P(cnt+1,ti[j]));
	G[cnt+1].push_back(P(cnt,ti[j]));
      }

      memo[s[j]].push_back(cnt);
      
      itos[cnt]=s[j];
      
      cnt++;
      
    }
    
  }

  n=cnt;

  P ans=dijkstra();

  if(ans.first==-1) cout<<-1<<endl;
  else cout<<ans.first<<' '<<ans.second<<endl;
  
  return 0;
}