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 N 50001
#define M 100011
#define f first
#define s second
#define INF (1e9)
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
int n,m,T;
vector<PP> G[M]; // to,cost,y,x
vector<int> g[M];
vector<P> D[M];

struct edge{
  int cost,cnt,y,x;
  bool operator > (edge a)const{return P(cost,cnt)>P(a.cost,a.cnt);}
};

priority_queue<edge,vector<edge>,greater<edge> >Q;  
P dijkstra(int a,int b){

  while(!Q.empty()){
    edge t=Q.top();Q.pop();
    int cost=t.cost,cnt=t.cnt;
    int y=t.y, x=t.x;
    int pos=g[y][x];
    if(D[y][x]<P(cost,cnt))continue;
    if(pos==b) return P(cost,cnt);
    
    for(int i=0;i<G[pos].size();i++){
      PP e=G[pos][i];
      int ncost=cost+e.f.s,ncnt=cnt;
      int ny=e.s.f,nx=e.s.s;
      if(pos!=a&&(ny!=y||abs(x-nx)!=1)) ncost+=T,ncnt++;
      if(D[ny][nx]>P(ncost,ncnt)){
	D[ny][nx]=P(ncost,ncnt);
	Q.push((edge){ncost,ncnt,ny,nx});
      }
    }
  }
  return P(-1,-1);
}

int main(){
  string s,t;
  cin>>m>>T>>s>>t;
  map<string,int> mp;
  mp[s]=n++;
  mp[t]=n++;

  for(int i=0,a;i<m;i++){
    cin>>a;
    D[i].resize(a,P(INF,INF));
    for(int j=0;j<a;j++){
      string str;
      cin>>str;
      if(!mp.count(str))mp[str]=n++;
      if(str==s)D[i][j]=P(0,0);
      if(str==s&&Q.empty())Q.push((edge){0,0,i,j});
      g[i].push_back(mp[str]);
    }

    for(int j=0,pre=g[i][0],cost;j<a-1;j++){
      cin>>cost;
      int pos=g[i][j+1];
      G[pre].push_back(PP(P(pos,cost),P(i,j+1)));
      G[pos].push_back(PP(P(pre,cost),P(i,j)));
      pre=pos;
    }
  }

  P ans=dijkstra(0,1);
  if(ans==P(-1,-1)) cout<<-1<<endl;
  else cout<<ans.f<<" "<<ans.s<<endl;
  return 0;
}