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<string> str[M];
vector<P> D[M];
map<string,int> mp;

P dijkstra(int s,int g){
  priority_queue<PP,vector<PP>,greater<PP> >Q;
  set<P> S;
  for(int i=0;i<m;i++)
    for(int j=0;j<str[i].size();j++)if(mp[str[i][j]]==s)S.insert(P(i,j)),D[i][j]=P(0,0);
  
  for(int i=0;i<G[s].size();i++){
      PP e=G[s][i];
      int ncost=e.f.s,ncnt=0;
      int ny=e.s.f,nx=e.s.s;
      if(!S.count(P(ny,nx-1))&&!S.count(P(ny,nx+1))) ncost+=T,ncnt=1;
      if(D[ny][nx]>P(ncost,ncnt))
	D[ny][nx]=P(ncost,ncnt),Q.push(PP(D[ny][nx],P(ny,nx)));
  }

  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=mp[str[y][x]];
    if(D[y][x]<t.f) continue;
    if(pos==g) 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(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);
}

void add_edge(vector<int> &cost,int i){
  int pre= mp.count(str[i][0])? mp[str[i][0]]:mp[str[i][0]]=n++;
  for(int j=0;j<cost.size();j++){
    int pos=mp.count(str[i][j+1])?mp[str[i][j+1]]:mp[str[i][j+1]]=n++;
    G[pre].push_back(PP(P(pos,cost[j]),P(i,j+1)));
    G[pos].push_back(PP(P(pre,cost[j]),P(i,j)));
    pre=pos;
  }
}

int main(){
  string s,g;
  cin>>m>>T>>s>>g;
  mp[s]=n++,mp[g]=n++;
  for(int i=0,a;i<m;i++){
    cin>>a;
    str[i].resize(a);
    D[i].resize(a,P(INF,INF));
    vector<int> cost(a-1);
    for(int j=0;j<a;j++)cin>>str[i][j];      
    for(int j=0;j<a-1;j++)cin>>cost[j];
    add_edge(cost,i);
  }

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