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 pair<int,int> P;
typedef pair< P , int > PP;
struct edge{int to,cost,type,id;};
int m,n,T,cnt,si,ti;
string str;
vector< edge > G[300005];
P d[300005];
int v[100005],w[100005];
edge p[200005];
map<string,int> mp;

int change(string &str){
  if(mp.count(str))return mp[str];
  else return mp[str]=mp.size();
}

int main(){
  cin>>m>>T;
  cin>>str;si=change(str);
  cin>>str;ti=change(str);
  for(int i=0;i<m;i++){
    cin>>n;
    for(int j=0;j<n;j++){
      cin>>str;
      v[j]=change(str);
    }
    for(int j=0;j+1<n;j++){
      cin>>w[j];
      G[v[j]].push_back((edge){v[j+1],w[j],i,++cnt});
      p[cnt]=G[v[j]].back();
    }
    for(int j=n-2;j>=0;j--){
      G[v[j+1]].push_back((edge){v[j],w[j],i,++cnt});
      p[cnt]=G[v[j+1]].back();
    }
  }
  int C=mp.size();
  fill(d,d+300005,P(1e9,1e9));
  d[0]=P(0,0);  
  priority_queue<PP,vector<PP>,greater<PP> > Q;
  Q.push(PP(P(-T,-1),1));
  P ans=P(-1,-1);
  while(!Q.empty()){
    PP q=Q.top();Q.pop();
    if(q.first>d[q.second])continue;
    P cost=q.first;
    int pos=q.second;
    if(pos==ti){
      ans=cost;
      break;
    }
    if(q.second<=C){
      for(int i=0;i<(int)G[pos].size();i++){
        edge e=G[pos][i];
        P ncost=cost;
        ncost.first+=(e.cost+T);
        ncost.second++;
        if(ncost<d[e.id+C]){
          d[e.id+C]=ncost;
          Q.push(PP(ncost,e.id+C));
        }
      }
    }else{
      edge f=p[pos-C];
      if(cost<d[f.to]){
        d[f.to]=cost;
        Q.push(PP(cost,f.to));
      }
      for(int i=-1;i<=1;i+=2){
        if(f.id+i<=0||cnt<f.id+i)continue;
        edge e=p[f.id+i];
        if(e.type!=f.type)continue;
        P ncost=cost;
        ncost.first+=e.cost;
        if(ncost<d[e.id+C]){
          d[e.id+C]=ncost;
          Q.push(PP(ncost,e.id+C));
        }
      }
    }
  }
  if(ans.first==-1)cout<<-1<<endl;
  else cout<<ans.first<<' '<<ans.second<<endl;
  return 0;
}