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<iostream>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
#include<queue>

using namespace std;

struct S{
  int x,l,o,t,n;
  bool operator<(S s)const{
    return (t!=s.t)?t>s.t:n>s.n;
  }
};

vector<string> names;
set<int> lines[123456];
set<int> u[123456][2];
vector<string> s[52345];
vector<int> t[52345];
map<int,set<int> > idtox[52345];

int to_num(string s){
  return lower_bound(begin(names),end(names),s)-begin(names);
}


int main(){
  int N,T;
  cin>>N>>T;
  string A,B;
  cin>>A>>B;
  priority_queue<S> que;
  for(int i=0;i<N;i++){
    int a;
    cin>>a;
    s[i].resize(a);
    for(int j=0;j<a;j++){
      cin>>s[i][j];
      names.push_back(s[i][j]);
      if(s[i][j]==A){
	que.push({j,i,1,0,0});
      }
    }
    t[i].resize(a-1);
    for(int j=0;j<a-1;j++){
      cin>>t[i][j];
    }
  }
  sort(begin(names),end(names));
  names.erase(unique(begin(names),end(names)),end(names));
  for(int i=0;i<N;i++){
    for(auto e:s[i]){
      lines[to_num(e)].insert(i);
    }
    for(int j=0;j<s[i].size();j++){
      idtox[i][to_num(s[i][j])].insert(j);
    }
  }
  while(!que.empty()){
    auto c=que.top();
    if(s[c.l][c.x]==(B))break;
    que.pop();
    if(!u[c.x][c.o].insert(c.l).second)continue;
    if(c.o){
      que.push({c.x,c.l,0,c.t,c.n});
      auto &hset=idtox[c.l][to_num(s[c.l][c.x])];
      auto hit=hset.lower_bound(c.x);
      if(hit!=hset.begin()){
	auto fhit=hit;
	que.push({*--fhit,c.l,1,c.t,c.n});
      }
      auto hbit=hit;
      if(++hbit!=hset.end()){
	que.push({*hbit,c.l,1,c.t,c.n});
      }
      int id=to_num(s[c.l][c.x]);
      auto &lset=lines[id];
      auto it=lset.lower_bound(c.l);
      if(it!=lset.begin()){
	auto fit=it;
	--fit;
	que.push({*idtox[*fit][id].begin(),*fit,1,c.t,c.n});
      }
      auto bit=it;
      if(++bit!=lset.end()){
	que.push({*idtox[*bit][id].begin(),*bit,1,c.t,c.n});
      }
    }else{
      if(c.x){
	que.push({c.x-1,c.l,0,c.t+t[c.l][c.x-1],c.n});
      }
      if(c.x!=t[c.l].size()){
	que.push({c.x+1,c.l,0,c.t+t[c.l][c.x],c.n});
      }
      que.push({c.x,c.l,1,c.t+T,c.n+1});
    }
  }
  if(que.empty()){
    cout<<-1<<endl;
  }else{	
    cout<<que.top().t<<' '<<que.top().n<<endl;
  }
}