Classic Dijkstra Algorithm!

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;
const int INF = 0x3f3f3f3f;
using P = pair<char, int>;
using PII = pair<int, char>;

int p, w;
char u, v;

void printGraph(unordered_map<char, vector<P>>& g) {
  for (auto&& [kk, vv] : g) {
    printf("%c: [", kk);
    for (const auto& [v, w] : vv) printf("(%c, %d) ", v, w);
    printf("]\n");
  }
}

// classic dijkstra's algorithm（优先队列优化版本-- 适用于稀疏图）
// 但这道题图中最多52个顶点。至多1E4条边 （Edges > Vertex ^ 2）, 边的数量远远大于顶点的数量。
// 因此是稠密图 应该用朴素(Naive)的dijkstra算法。但我偏用优先队列优化版的。反正也AC了！！
void dijkstra(unordered_map<char, vector<P>>& g, unordered_map<char, int>& dists) {
  priority_queue<PII, vector<PII>, greater<PII>> pq;
  pq.emplace(0, 'Z');
  unordered_set<char> seen;

  while (not pq.empty()) {
    const auto [d, u] = pq.top(); pq.pop();
    if (seen.count(u)) continue;
    seen.emplace(u);

    for (const auto& [v, w] : g[u]) {
      if (seen.count(v)) continue;
      if (d + w < dists[v]) {
        dists[v] = d + w;
        pq.emplace(d + w, v);
      }
    }
  }
}

int main(void) {
  scanf("%d", &p);
  unordered_map<char, vector<P>> g;
  unordered_map<char, int> dists;

  // 懒的推公式了, 反正最多52次 CTRL+C, CTRL+V 很香的!
  dists['a'] = INF;
  dists['b'] = INF;
  dists['c'] = INF;
  dists['d'] = INF;
  dists['e'] = INF;
  dists['f'] = INF;
  dists['g'] = INF;
  dists['h'] = INF;
  dists['i'] = INF;
  dists['j'] = INF;
  dists['k'] = INF;
  dists['l'] = INF;
  dists['m'] = INF;
  dists['n'] = INF;
  dists['o'] = INF;
  dists['p'] = INF;
  dists['q'] = INF;
  dists['r'] = INF;
  dists['s'] = INF;
  dists['t'] = INF;
  dists['u'] = INF;
  dists['v'] = INF;
  dists['w'] = INF;
  dists['x'] = INF;
  dists['y'] = INF;
  dists['z'] = INF;

  dists['A'] = INF;
  dists['B'] = INF;
  dists['C'] = INF;
  dists['D'] = INF;
  dists['E'] = INF;
  dists['F'] = INF;
  dists['G'] = INF;
  dists['H'] = INF;
  dists['I'] = INF;
  dists['J'] = INF;
  dists['K'] = INF;
  dists['L'] = INF;
  dists['M'] = INF;
  dists['N'] = INF;
  dists['O'] = INF;
  dists['P'] = INF;
  dists['Q'] = INF;
  dists['R'] = INF;
  dists['S'] = INF;
  dists['T'] = INF;
  dists['U'] = INF;
  dists['V'] = INF;
  dists['W'] = INF;
  dists['X'] = INF;
  dists['Y'] = INF;
  dists['Z'] = 0; // 牛棚到牛棚的距离

  while (p--) {
    scanf("%s %s %d", &u, &v, &w);
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }

  dijkstra(g, dists);

  char ans = 0; 
  int min_dist = INF;
  const string s = "ABCDEFGHIJKLMNOPQRSTUVWXY";
  for (const auto& c : s)
    if (dists[c] < min_dist) ans = c, min_dist = dists[c];

  return printf("%c %d\n", ans, min_dist), 0;
}