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
vector<int> g[M]; 
vector<P> D[M];

priority_queue<PP,vector<PP>,greater<PP> >Q;  
P dijkstra(int a,int b){
  while(!Q.empty()){
    PP t=Q.top();Q.pop();
    int cost=t.f.f,cnt=t.f.s;
    int y=t.s.f, x=t.s.s;
    int pos=g[y][x];
    if(D[y][x]<t.f) continue;
    if(pos==b) return t.f;
    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(PP(D[ny][nx],P(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(PP(P(0,0),P(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;
}