思路
dijkstra,哈希了一下字母,注意题意就行
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#define _fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(e) push_back(e)
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define endl '\n'
using namespace std;
using i64 = long long;
using PII = pair<int,int>;
const int INF = 0x3f3f3f3f;
unordered_map<string,int> S;
unordered_map<int,string> RS;
int z,idx;
const int N = 10010;
int get(string s)
{
if(S.count(s) == 0) S[s] = ++ idx,RS[idx] = s;
return S[s];
}
int main()
{
int n = 26 * 2 + 1;
int m;
cin >> m;
vector<PII> h[N];
while(m -- )
{
string a,b;
int w;
cin >> a >> b >> w;
int x = get(a);
int y = get(b);
if(a == "Z") z = x;
if(b == "Z") z = y;
h[x].push_back({y,w});
h[y].push_back({x,w});
}
vector<int> dis(n + 1, 0x3f3f3f3f);
auto dijkstra = [&](int s = 1) ->void {
int y, w;
using PII = pair<int,int>;
priority_queue<PII,vector<PII>,greater<PII> > q;
q.emplace(0, s);
dis[s] = 0;
vector<int> st(n + 1);
while (q.size()) {
int x = q.top().second;
q.pop();
if (st[x]) continue;
st[x] = 1;
for (auto el : h[x]) {
tie(y, w) = el;
if (dis[y] > dis[x] + w) {
dis[y] = dis[x] + w;
q.emplace(dis[y], y);
}
}
}
};
dijkstra(z);
int ans = INF,id = -1;
for(int i=1;i<=idx;++i)
{
if(dis[i] < ans && i != z && isupper(RS[i].c_str()[0]))
{
ans = dis[i];
id = i;
}
}
cout << RS[id] << ' ' << dis[id] << endl;
return 0;
}