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>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF P(1e16,1e16)

struct edge{
  ll to;
  P cost;
};

struct state{
  ll v;
  P cost;
};
bool operator<(const state& a,const state& b){ return a.cost > b.cost; }

ll n,M,T;
vector<edge> g[201010];
string A,B;
map<string,vector<ll> > name;
P dist[201010];

int main(){
	cin.sync_with_stdio(false);
  cin>>M>>T>>A>>B;

  // on line
  rep(i,M){
    ll num;
    vector<string> ss;
    vector<ll> ts;
    cin>>num;
    rep(j,num){
      string s;
      cin>>s;
      ss.push_back(s);
    }
    rep(j,num-1){
      ll t;
      cin>>t;
      ts.push_back(t); 
    }
    rep(j,num-1){
      g[n+j].push_back((edge){n+j+1,P(ts[j],0)});
      g[n+j+1].push_back((edge){n+j,P(ts[j],0)});
    }
    rep(j,num)name[ss[j]].push_back(n++);
  }

  // out
  for(auto it : name){
    for(int vs : it.se){
      g[n].push_back((edge){vs,P(T,1)});
      g[vs].push_back((edge){n,P(0,0)});
    }
    name[it.fi].push_back(n++);
  }

  /*
  dbg(n);
  for(auto it : name){
    dbg(it.fi);
    for(int v : it.se){
      dbg(v);
    }
  }*/

  rep(i,201010)dist[i]=INF;
  priority_queue<state> que;
  for(int vs : name[A]){
    que.push((state){vs,P(0,0)});
  }
  while(que.size()){
    ll v = que.top().v; P cost = que.top().cost; que.pop();
    if(dist[v]!=INF)continue;
    dist[v]=cost;
    for(edge e : g[v]){
      que.push((state){e.to,P(cost.fi+e.cost.fi,cost.se+e.cost.se)});
    }
  }
  P res=INF;
  for(int vs : name[B]){
    minch(res,dist[vs]);
  }
  if(res==INF)printf("-1\n");
  else printf("%lld %lld\n", res.fi,res.se);

	return 0;
}