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 <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <limits>
#include <cfloat>
#include <functional>
using namespace std;

template <class T>
class Edge
{
public:
    int to;
    T cost;
    Edge(){};
    Edge(int to0, T cost0){to = to0; cost = cost0;}
};

template<class T>
void shortestPath(const vector<vector<Edge<T> > >& edges, int start, vector<T>& dist)
{
    const T INF = numeric_limits<T>::max();
    const T EPS = static_cast<T>(1.0e-10);

    dist.assign(edges.size(), INF);
    dist[start] = 0;
    priority_queue<pair<T,int>, vector<pair<T,int> >, greater<pair<T,int> > > q;
    q.push(make_pair(0, start));

    while(!q.empty()){
        pair<T, int> p = q.top();
        q.pop();
        int v = p.second;
        if(dist[v] < p.first - EPS)
            continue;
        for(unsigned i=0; i<edges[v].size(); ++i){
            Edge<T> e = edges[v][i];
            if(dist[v] + e.cost < dist[e.to] - EPS){
                dist[e.to] = dist[v] + e.cost;
                q.push(make_pair(dist[e.to], e.to));
            }
        }
    }
}

const long long X = 100000;

int main()
{
    int n, transferTime;
    string start, goal;
    cin >> n >> transferTime >> start >> goal;

    vector<int> a(n);
    vector<vector<string> > s(n);
    vector<vector<int> > t(n);
    map<string, int> index;

    for(int i=0; i<n; ++i){
        cin >> a[i];
        s[i].resize(a[i]);
        for(int j=0; j<a[i]; ++j){
            cin >> s[i][j];
            index[s[i][j]];
        }

        t[i].resize(a[i]-1);
        for(int j=0; j<a[i]-1; ++j)
            cin >> t[i][j];
    }

    int m = 0;
    for(map<string, int>::iterator it=index.begin(); it!=index.end(); ++it){
        it->second = m;
        ++ m;
    }

    vector<vector<Edge<long long> > > edges(m + accumulate(a.begin(), a.end(), 0));
    int p = m;
    for(int i=0; i<n; ++i){
        for(int j=0; j<a[i]; ++j){
            edges[p+j].push_back(Edge<long long>(index[s[i][j]], transferTime * X + 1));
            edges[index[s[i][j]]].push_back(Edge<long long>(p+j, 0));
        }
        for(int j=0; j<a[i]-1; ++j){
            edges[p+j].push_back(Edge<long long>(p+j+1, t[i][j] * X));
            edges[p+j+1].push_back(Edge<long long>(p+j, t[i][j] * X));
        }
        p += a[i];
    }

    vector<long long> dist;
    shortestPath(edges, index[start], dist);
    long long ret = dist[index[goal]];
    
    if(ret == LLONG_MAX){
        cout << -1 << endl;
    }else{
        ret -= (transferTime * X + 1);
        cout << (ret / X) << ' ' << (ret % X) << endl;
    }

    return 0;
}