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;
set<PP> G[M]; // to,cost,y,x
vector<int> g[M],c[M];
vector<P> D[M];
priority_queue<PP,vector<PP>,greater<PP> >Q;  
P dijkstra(int a,int b){
  vector<int>used(n,0);

  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;


    if(used[pos]++){
      if(x+1<g[y].size()){
	int ncost=cost+c[y][x],ncnt=cnt;
	int ny=y,nx=x+1;
	if(D[ny][nx]>P(ncost,ncnt)){
	  D[ny][nx]=P(ncost,ncnt);
	  Q.push(PP(D[ny][nx],P(ny,nx)));
	}
      }
      if(x-1>=0){
	int ncost=cost+c[y][x-1],ncnt=cnt;
	int ny=y,nx=x-1;
	if(D[ny][nx]>P(ncost,ncnt)){
	  D[ny][nx]=P(ncost,ncnt);
	  Q.push(PP(D[ny][nx],P(ny,nx)));
	}
      }
      continue;
    }
    
    for(set<PP>::iterator i=G[pos].begin();i!=G[pos].end();i++){
      int ncost=cost+i->f.s,ncnt=cnt;
      int ny=i->s.f,nx=i->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)));
      }
    }
    used[pos]++;
  }
  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]);
    }

    c[i].resize(a-1);
    for(int j=0,pre=g[i][0];j<a-1;j++){
      cin>>c[i][j];
      int pos=g[i][j+1];
      G[pre].insert(PP(P(pos,c[i][j]),P(i,j+1)));
      G[pos].insert(PP(P(pre,c[i][j]),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;
}