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 inf (long long)(1e16)
using namespace std;

struct node {
  int n;
  long long time, change;
  bool operator<(const node &r) const {
    if(time != r.time) return time > r.time;
    return change > r.change;
  }
  bool operator!=(const node &r) const {
    return n != r.n || time != r.time || change != r.change;
  }
};

struct edge {
  long long to, time;
};

long long n, t, cnt = 0, stations = 2;
string a, b;
map<string, int> mp;
vector<int> smemo;
vector<vector<int>> id;
vector<vector<edge>> edges;
vector<bool> added;
vector<node> dist;
priority_queue<node> pq;

void solve();

int main() {
  cin >> n >> t >> a >> b;
  mp[a] = 0;
  mp[b] = 1;
  id.resize(2);
  for(int i = 0; i < n; ++i) {
    long long x;
    cin >> x;
    for(int j = 0; j < x; ++j) {
      string str;
      cin >> str;
      if(mp.find(str) == mp.end()) {
        ++stations;
        mp[str] = id.size();
        id.push_back(vector<int>(0));
        assert(mp.size() == id.size());
      }
      edges.push_back(vector<edge>(0));
      smemo.push_back(mp[str]);
      id[mp[str]].push_back(cnt++);
      assert(smemo.size() == cnt);
    }
    for(int j = 0; j < x - 1; ++j) {
      long long nt;
      cin >> nt;
      edges[cnt - x + j].push_back({cnt - x + j + 1, nt});
      edges[cnt - x + j + 1].push_back({cnt - x + j, nt});
    }
  }
  solve();
  return 0;
}

void solve() {
  node res = {-1, inf, inf};
  added.assign(stations, 0);
  added[0] = 1;
  dist.assign(cnt, res);
  for(auto p : id[0]) {
    pq.push({p, 0, 0});
    dist[p] = {p, 0, 0};
  }
  while(pq.size()) {
    node now = pq.top();
    pq.pop();
    if(dist[now.n] != now) continue;
    if(!added[smemo[now.n]]) {
      added[smemo[now.n]] = 1;
      node nextp = now;
      ++nextp.change;
      nextp.time += t;
      for(auto p : id[smemo[now.n]])
        if(dist[p] < nextp) {
          nextp.n = p;
          dist[p] = nextp;
          pq.push(nextp);
        }
    }
    for(auto e : edges[now.n]) {
      node nextp = now;
      nextp.n = e.to;
      nextp.time += e.time;
      if(dist[nextp.n] < nextp) {
        dist[nextp.n] = nextp;
        pq.push(nextp);
      }
    }
  }
  for(auto p : id[1]) res = max(res, dist[p]);
  if(res.n == -1)
    cout << -1 << endl;
  else
    cout << res.time << " " << res.change << endl;
}