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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct Edge {
  int from;
  int to;
  ll cost;
  ll change;
  Edge() {;}
  Edge(int from, int to, ll cost, ll change) :
    from(from), to(to), cost(cost), change(change) {;}
  bool operator<(const Edge &rhs) const {
    if (cost != rhs.cost) { return cost > rhs.cost; }
    return change > rhs.change;
  }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

char str[10000];
int n, t;
map<string, int> mapto;
vector<vector<int> > station;
vector<vector<int> > costs;
int m;
int SIZE;

int main() {
  while (scanf("%d %d", &n, &t) > 0) {
    SIZE = 0;
    m = 0;
    mapto.clear();
    scanf("%s", str);
    mapto[str] = m++;
    scanf("%s", str);
    mapto[str] = m++;
    station.clear();
    costs.clear();
    station.resize(n);
    costs.resize(n);
    REP(i, n) {
      int k;
      scanf("%d", &k);
      SIZE += k;
      REP(j, k) {
        scanf("%s", str);
        if (!mapto.count(str)) { mapto[str] = m++; }
        station[i].push_back(mapto[str]);
      }
      REP(j, k - 1) {
        int c;
        scanf("%d", &c);
        costs[i].push_back(c);
      }
    }
    SIZE += m;
    Graph g(SIZE);
    {
      int from = m;
      REP(i, n) {
        REP(j, station[i].size()) {
          g[station[i][j]].push_back(Edge(station[i][j], from, t, 1));
          g[from].push_back(Edge(from, station[i][j], 0, 0));
          if (j != 0) {
            g[from - 1].push_back(Edge(from - 1, from, costs[i][j - 1], 0));
            g[from].push_back(Edge(from, from - 1, costs[i][j - 1], 0));
          }
          from++;
        }
      }
    }

    priority_queue<Edge> que;
    que.push(Edge(0, 0, 0, 0));
    vector<char> visit(SIZE);
    vector<ll> dist(SIZE, 1LL << 60) ;
    while (!que.empty()) {
      Edge e = que.top();
      que.pop();
      int from = e.to;
      if (visit[from]) { continue; }
      visit[from] = true;
      if (from == 1) {
        printf("%lld %lld\n", e.cost - t, e.change - 1);
        goto next;
      }
      FORIT(it, g[e.to]) {
        int to = it->to;
        ll ncost = it->cost + e.cost;
        ll nchange = it->change + e.change;
        if (visit[to]) { continue; }
        if (dist[to] < ncost) { continue; }
        dist[to] = ncost;
        que.push(Edge(from, to, ncost, nchange));
      }
    }
    puts("-1");
next:;
  }
}