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 r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;

int N,T,x[200009],n;
map<int,int>a[200009];
set<string>st;
vector<P2>v[200009];
string start,goal,str[200009];
map<int,string> s[200009];
P dis[200099];

int main(){
    cin>>N>>T;
    cin>>start>>goal;
    st.insert(start);
    st.insert(goal);
    r(i,N){
        cin>>x[i];
        r(j,x[i]){
            cin>>s[i][j];
            str[n+j]=s[i][j];
            a[i][j]=n+j;
            st.insert(s[i][j]);
        }
        r(j,x[i]-1){
            int y;
            cin>>y;
            v[n+j].push_back(P2(n+j+1,P(y,0)));
            v[n+j+1].push_back(P2(n+j,P(y,0)));
        }
        n+=x[i];
    }
    map<string,int>M;
    for(set<string>::iterator it=st.begin();it!=st.end();it++){
        string x=*it;
        str[n]=x;
        M[x]=n++;
    }
    r(i,N){
        r(j,x[i]){
            int y=M[s[i][j]];
            v[a[i][j]].push_back(P2(y,P(T,1)));
            v[y].push_back(P2(a[i][j],P(0,0)));
        }
    }
    priority_queue<P2,vector<P2>,greater<P2> >q;
    r(i,200099)dis[i]=P(1e9,1e9);
    r(i,n-st.size()){
        if(str[i]==start){
            q.push(P2(0,P(0,i)));
            dis[i]=P(0,0);
        }
    }
    while(!q.empty()){
        P2 p=q.top();q.pop();
        int now=p.second.second;
        int cost=p.first;
        int nori=p.second.first;
        if(dis[now]<P(cost,nori))continue;
        r(i,v[now].size()){
            int nex=v[now][i].first;
            int ncost=v[now][i].second.first+cost;
            int nnori=v[now][i].second.second+nori;
            P NEX=P(ncost,nnori);
            if(NEX<dis[nex]){
                dis[nex]=NEX;
                q.push(P2(ncost,P(nnori,nex)));
            }
        }
    }
    P ans=P(1e9,1e9);
    r(i,n-st.size()){
        if(str[i]==goal){
            ans=min(ans,dis[i]);
        }
    }
    if(ans==P(1e9,1e9))cout<<-1<<endl;
    else cout<<ans.first<<' '<<ans.second<<endl;
}