Distanta

#include <fstream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
#define INF 0x3F3F3F3F
using namespace std;
unordered_map<string,int>mp;
unordered_map<int,string>mp1;
ifstream in("distanta.in");
ofstream out("distanta.out");
string s;
int n,m;
vector<int>d,dist,t;
vector<pair<int,int>>g[21];
int p,q;
int dp[21][21];

long long bfs(int node)
{
    queue<int>coada;
    coada.push(node);
    d[node]=0;
    int ok=0;
    while(!coada.empty())
    {
        int node=coada.front();
        coada.pop();
        for(auto& i:g[node])
        {
            if(!ok&&i.first==q)
                continue;
            int tmp=i.second+d[node];
            if(d[i.first]>=tmp)
                d[i.first]=tmp,t[i.first]=node,coada.push(i.first);
        }
        ++ok;
    }
    return d[q];
}

int main()
{
    in>>n;
    d=t=vector<int>(n+1);
    dist=vector<int>(n+1);
    for(int i=1;i<=n;++i)
        t[i]=i,in>>s>>d[i],dist[i]=d[i],mp[s]=i,mp1[i]=s;
    in>>m;
    for(int i=0;i<m;++i)
    {
        string a,b;
        int c;
        in >>a>>b>>c;
        int cost=c+d[mp[a]]+d[mp[b]];
        dp[mp[a]][mp[b]]=cost;
        dp[mp[b]][mp[a]]=cost;
        g[mp[a]].push_back(make_pair(mp[b],cost));
        g[mp[b]].push_back(make_pair(mp[a],cost));
    }
    string a,b;
    in>>a>>b;
    p=mp[a];
    q=mp[b];
    d=vector<int>(n+1,INF);
    long long maxi=bfs(p);
    if(maxi==INF)
        out<<"NU EXISTA TRASEU";
    else
    {
        vector<int>ans;
        int aux=q;
        while(t[q]!=q)
            ans.push_back(q),q=t[q],maxi-=dist[q];
        q=aux;
        if(maxi+dist[p]>dp[p][q]&&dp[p][q])
            out<<dp[p][q]<<'\n'<<mp1[p]<<'\n'<<mp1[q]<<'\n';
        else
        {
            out<<maxi+dist[p]<<'\n';
            out<<a<<'\n';
            for(vector<int>::reverse_iterator it=ans.rbegin();it!=ans.rend();++it)
                out<<mp1[*it]<<'\n';
        }
    }
    return 0;
}