这个蒟蒻不想用图论算法
我这个代码用DFS反着推，样例能过，剩下不知炸哪了
烂码：

#include <bits/stdc++.h>
using namespace std;
struct p {
	int x;
	int v;
};
vector<p> r[27];
int g[27];
bool flag[27];
bool vis[27];
int getc(char x) {
	if(x >= 'a' && x <= 'z') {
		return x - 'a';
	}
	else {
		return x - 'A';
	}
}
void dfs(int x, int fa, int road) {
	vis[x] = true;
	g[x] = road;
	for (int i = 0; i < r[x].size(); i++) {
		int to = r[x][i].x;
		if (to != fa && !vis[to] && road + r[x][i].v < g[to]) {
			dfs(to, x, road + r[x][i].v);
		}
	}
	vis[x] = false;
}
int main() {
	int p;
	cin >> p;
	for (int i = 0; i < 26; i++) {
		g[i] = 114514;
		flag[i] = false;
		vis[i] = false;
	}
	for (int i = 1; i <= p; i++) {
		char xx, yy;
		int k;
		cin >> xx >> yy >> k;
		int x = getc(xx);
		int y = getc(yy);
		if (xx >= 'A' && xx <= 'Z') flag[x] = true;
		if (yy >= 'A' && yy <= 'Z') flag[y] = true;
		if (x == 25 && y == 25) continue;
		r[x].push_back({y, k});
		r[y].push_back({x, k});
	}
	dfs(25, -1, 0);
	int ans = 114514, ans_id = 0;
	for (int i = 0; i < 25; i++) {
		if (flag[i] && (g[i] < ans || (g[i] == ans && i < ans_id))) {
			ans = g[i];
			ans_id = i;
		}
	}
	cout << (char)(ans_id + 'A') << ' ' << ans;
	return 0;
}

（看不懂问我，每日在线）