USACO-T038: Bessie Come Home

/*
ID: mickyta1
TASK: comehome
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
typedef pair<char, int> pci;
typedef pair<int, char> pic;

vector<pci> adj[2][26];
int dist[2][26];
bool visited[2][26];

vector<pci> &adjAcc(char c){
    if(isupper(c)){
        return adj[0][c - 'A'];
    } else {
        return adj[1][c - 'a'];
    }
}

int &distAcc(char c){
    if(isupper(c)){
        return dist[0][c - 'A'];
    } else {
        return dist[1][c - 'a'];
    }
}

bool &visitedAcc(char c){
    if(isupper(c)){
        return visited[0][c - 'A'];
    } else {
        return visited[1][c - 'a'];
    }
}

int main(){
    freopen("comehome.in", "r", stdin);
    freopen("comehome.out", "w", stdout);

    int nEdge;
    scanf("%d", &nEdge);
    for(int i = 1; i <= nEdge; ++i){
        char u, v;
        int w;
        scanf(" %c %c%d", &u, &v, &w);
        adjAcc(u).emplace_back(v, w);
        adjAcc(v).emplace_back(u, w);
    }
    for(int i = 0; i < 26; ++i){
        dist[0][i] = 1e9;
        dist[1][i] = 1e9;
    }
    priority_queue<pic, vector<pic>, greater<pic>> pq;
    distAcc('Z') = 0;
    pq.emplace(distAcc('Z'), 'Z');
    while(!pq.empty()){
        char u = pq.top().s;
        pq.pop();
        if(isupper(u) && u != 'Z'){
            cout << u << ' ' << distAcc(u) << '\n';
            fclose(stdin);
            fclose(stdout);
            return 0;
        }
        if(visitedAcc(u)){
            continue;
        }
        visitedAcc(u) = true;
        for(pci nxt : adjAcc(u)){
            char v = nxt.f;
            int w = nxt.s;
            if(!visitedAcc(v) && distAcc(u) + w < distAcc(v)){
                distAcc(v) = distAcc(u) + w;
                pq.emplace(distAcc(v), v);
            }
        }
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}