团体程序设计天梯赛 L3-011 直捣黄龙 (30分)

题目链接：

L3-011 直捣黄龙 (30分)

思路：

很复杂的变形，最短路就使用dijkstra，注意细节就好

代码：

#include<bits/stdc++.h>

using namespace std;

inline int toi(string & s) { 
	return s[0] - 'A' + (s[1] - 'A' << 5) + (s[2] - 'A' << 10);
}
inline string tos(int x) {
	string s = "";
	for(int i = 0; i < 3; i++) s += x % 32 + 'A', x >>= 5;
	return s;	
}
const int maxn = 26 << 11;
struct edge { int to, c; };
int s, t, n, k, ans[maxn], num[maxn], d[maxn], lib[maxn], kll[maxn], par[maxn];
vector<edge> G[maxn];

#define update() d[u] = d[v] + e.c, lib[u] = lib[v] + 1, kll[u] = kll[v] + num[u], par[u] = v, que.push(P(d[u], u));
typedef pair<int, int> P;
void dijkstra() {
	fill(d, d + maxn, 1 << 30);
	d[s] = 0, ans[s] = 1;
	priority_queue<P, vector<P>, greater<P> > que;
	que.push(P(0, s));
	while(!que.empty()) {
		P p = que.top();
		if(p.second == t) return;
		que.pop();
		int v = p.second;
		if(d[v] < p.first) continue;
		for(edge & e : G[v]) {
			int u = e.to;
			if(d[u] > d[v] + e.c) { 
				update();
				ans[u] = ans[v];
			}else if(d[u] == d[v] + e.c) {
				if(par[u] != v) ans[u] += ans[v];
				if(lib[u] == lib[v] + 1 ? kll[u] < kll[v] + num[u] : lib[u] < lib[v] + 1) {
					update();	
				}
			}	
		}
	}
}
void print_path(int u) {
	if(u == s) cout << tos(u);
	else print_path(par[u]), cout << "->" << tos(u);
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	int n, k, cost;
	string a, b, x;
	cin >> n >> k >> a >> b;
	s = toi(a), t = toi(b);
	for(int i = 1; i < n; i++) {
		cin >> x;
		cin >> num[toi(x)];
	}
	for(int i = 0; i < k; i++) {
		cin >> a >> b >> cost;
		int x = toi(a), y = toi(b);
		G[x].push_back({y, cost});
		G[y].push_back({x, cost});
	}
	dijkstra();
	print_path(t);
	cout << '
' << ans[t] << ' ' << d[t] << ' ' << kll[t];
	return 0;
}