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;  

void ifPush(int cost,int cnt,int y,int x){
  if(D[y][x]<=P(cost,cnt))return;
  D[y][x]=P(cost,cnt);
  Q.push(PP(D[y][x],P(y,x)));
}

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())ifPush(cost+c[y][x],cnt,y,x+1);
      if(x-1>=0)ifPush(cost+c[y][x-1],cnt,y,x-1);
      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++;
      ifPush(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));
    c[i].resize(a-1);
    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];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;
}