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 <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
using namespace std;

const int inf = 1<<29;

template<typename T>
class IdMap {
public:
    IdMap(int n = 0) : ridx(n) {;}

    void add(const T t) {
        _idx[t] = ridx.size();
        ridx.push_back(t);
    }

    int idx(const T &t) {
        if(_idx.find(t) == _idx.end()) add(t);
        return _idx[t];
    }
    T get(int i) { return ridx[i]; }

    int size() { return ridx.size(); }

private:
    map<T,int> _idx;
    vector<T> ridx;
};

struct Edge { int s,t,c,sw; };
bool operator<(const Edge &e,const Edge &f) {
    return e.c != f.c ? e.c > f.c : (e.sw != f.sw) ? e.sw > f.sw : e.s < f.s;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

#define rep(i,n) for(int i=0; i<(int)n; ++i)

vector<int> seg[100001];
vector<int> ridx;
int tr;

int spath(const Graph &g,int s,int t,IdMap<string> &id) {
    const int n = g.size();
    vector<int> dist(n, inf), prev(n, -1), sw(n, inf);

    priority_queue<Edge> q;
    for(int i=0; i<seg[s].size(); ++i) {
        q.push((Edge){-2,seg[s][i],0,0});
        dist[seg[s][i]] = 0;
        sw[seg[s][i]] = 0;
    }

    while(!q.empty()) {
        Edge e = q.top(); q.pop();

        if(prev[e.t] != -1) continue;
        prev[e.t] = e.s;

        rep(i,g[e.t].size()) {
            int v = g[e.t][i].t, c = g[e.t][i].c;
            if(prev[v] != -1) continue;
            if(dist[v] > e.c + c) {
                dist[v] = e.c + c;
                sw[v] = e.sw;
                q.push((Edge){e.t,v,c+e.c,e.sw+g[e.t][i].sw});
            }
        }
    }

    int ans = inf, aw = inf;
    for(int i=0; i<seg[t].size(); ++i) {
        if(ans > dist[seg[t][i]]) {
            ans = dist[seg[t][i]];
            aw = sw[seg[t][i]];
        }else if(ans == dist[seg[t][i]]) {
            aw = min(aw, sw[seg[t][i]]);
        }
    }
    if(ans == inf) {
        cout<<-1<<endl;
        return 0;
    }
    cout<<ans/2<<" "<<aw<<endl;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    int n,a;
    string A,B,in;

    rep(i,100001) seg[i] = vector<int>(0);

    cin>>n>>tr>>A>>B;
    Graph g;
    IdMap<string> id;

    int cnt = 0;
    for(int i=0; i<n; ++i) {
        cin>>a;
        vector<int> s(a),time(a);
        for(int j=0; j<a; ++j) {
            cin>>in;
            s[j] = id.idx(in);
            ridx.push_back(s[j]);
        }

        seg[s[0]].push_back(cnt);
        g.push_back(Edges(0));
        cnt++;

        for(int j=0; j<a-1; ++j) {
            cin>>time[j+1];
            seg[s[j+1]].push_back(cnt);
            g.push_back(Edges(0));
            g[cnt-1].push_back((Edge){cnt-1,cnt,time[j+1]*2,0});
            g[cnt].push_back((Edge){cnt,cnt-1,time[j+1]*2,0});
            cnt++;
        }
    }

    for(int i=0; i<id.size(); ++i) {
        g.push_back(Edges(0));
        for(int j=0; j<seg[i].size(); ++j) {
            g[seg[i][j]].push_back((Edge){seg[i][j],cnt,tr,0});
            g[cnt].push_back((Edge){cnt,seg[i][j],tr,1});
        }
        cnt++;
    }

    spath(g,id.idx(A),id.idx(B),id);
}