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 f first
#define s second
#define mp make_pair
#define MAX 100010
#define inf 1<<28
using namespace std;

typedef pair<int,int> pii;

class State{
public:
  int n,cost,sum;
  State(int n,int cost,int sum):n(n),cost(cost),sum(sum){}
  bool operator<(State s)const{
    if(cost!=s.cost)return s.cost<cost;
    return s.sum<sum;
  } 
};

vector<pair<int,int> > v[MAX];
int n,t,c[MAX];
string a,b,s[MAX];
set<int> st;
vector<int> start,end;
pii dis[MAX];
priority_queue<State> pq;
map<int,vector<int> > M;
map<string,int> Ma;
int canp[MAX];

pii dijkstra(){
  for(int i=0;i<MAX;i++){
    dis[i].f=inf;
    dis[i].s=inf;
  }

  for(int i=0;i<start.size();i++){
    pq.push(State(start[i],0,0));
    dis[start[i]]=mp(0,0);
  }

  while(!pq.empty()){
    State u=pq.top();
    pq.pop();

    if(st.find(u.n)!=st.end())return mp(u.cost,u.sum);

    if(dis[u.n]<mp(u.cost,u.sum))continue;

    for(int i=0;i<v[u.n].size();i++){
      int next=v[u.n][i].f,cost=dis[u.n].f+v[u.n][i].s,sum=dis[u.n].s;
      if(mp(cost,sum)<dis[next]){
	dis[next]=mp(cost,sum);
	pq.push(State(next,cost,sum));
      }
    }
    vector<int> vi=M[canp[u.n]];
    for(int i=0;i<vi.size();i++){
      if(vi[i]==u.n)continue;
      int next=vi[i],cost=dis[u.n].f+t,sum=dis[u.n].s+1;
      if(mp(cost,sum)<dis[next]){
	dis[next]=mp(cost,sum);
	pq.push(State(next,cost,sum));
      }
    }
  }
  return mp(-1,-1);
}

int main()
{
  int k,count1=0,count2=0;

  cin>>n>>t;
  cin>>a>>b;

  for(int i=0;i<n;i++){
    cin>>k;
    for(int j=0;j<k;j++)cin>>s[j];
    for(int j=0;j<k-1;j++)cin>>c[j];
    for(int j=0;j<k;j++){
      int con;
      if(Ma.find(s[j])==Ma.end()){
	count2++;
	con=count2;
	Ma[s[j]]=count2;
      }
      else con=Ma[s[j]];
      M[con].push_back(count1);
      canp[count1]=con;

      if(s[j]==a)start.push_back(count1);
      if(s[j]==b)st.insert(count1);

      if(j<k-1){
	v[count1].push_back(mp(count1+1,c[j]));
	v[count1+1].push_back(mp(count1,c[j]));
      }
      count1++;
    }
  }

  pii p=dijkstra();
  if(p==mp(-1,-1))cout<<-1<<endl;
  else cout<<p.f<<" "<<p.s<<endl;

  return 0;
}