思路:单源最短路末班就好了,字符串映射成数字处理。
AC代码
//#define LOCAL
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <string>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 200;
map<string, int> ha;
int id, st, ed;
int n, k;
int hap[maxn];
char names[maxn][50];
int getId(string s) {
if(!ha.count(s)) {
ha[s] = id++;
}
return ha[s];
}
struct Edge {
int from, to, dist;
Edge(int u, int v, int d):from(u),to(v),dist(d) {}
};
vector<Edge> edges;
vector<int> G[maxn];
bool done[maxn];
int d[maxn], hp[maxn], pt[maxn], routes[maxn]; //Best
int p[maxn];
void init() {
ha.clear();
id = 0;
for(int i = 0; i < maxn; i++) G[i].clear();
edges.clear();
}
void addEdge(int from, int to, int dist) {
edges.push_back(Edge(from, to, dist));
int m = edges.size();
G[from].push_back(m-1);
}
struct HeapNode{
int d, u;
HeapNode(int d, int u):d(d), u(u){
}
bool operator < (const HeapNode& rhs) const {
return d > rhs.d;
}
};
//距离小,开心多,平均大
void dijkstra(int s) {
memset(done, 0, sizeof(done));
priority_queue<HeapNode> Q;
for(int i = 0; i < n; i++) {
d[i] = inf;
hp[i] = -inf;
pt[i] = inf;
}
d[s] = hp[s] = pt[s] = 0;
routes[s] = 1;
Q.push(HeapNode(0, s));
while(!Q.empty()) {
HeapNode x = Q.top(); Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = 0; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
bool update = false;
if(d[e.to] > d[u] + e.dist) {
routes[e.to] = routes[u];
update = true;
} else if(d[e.to] == d[u] + e.dist) {
routes[e.to] += routes[u];
if(hp[e.to] < hp[u] + hap[e.to]) {
update = true;
} else if(hp[e.to] == hp[u] + hap[e.to]) {
if(pt[e.to] > pt[u] + 1) {
update = true;
}
}
}
if(update) {
d[e.to] = d[u] + e.dist;
p[e.to] = u;
hp[e.to] = hp[u] + hap[e.to];
pt[e.to] = pt[u] + 1;
Q.push(HeapNode(d[e.to], e.to));
}
}
}
}
void print(int u) {
if(u == 0) {
printf("%s", names[0]);
return;
} else {
print(p[u]);
printf("->%s", names[u]);
}
}
int main() {
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
while(scanf("%d%d%s", &n, &k, names[0]) == 3) {
init();
st = getId(names[0]);
int happy;
for(int i = 1; i < n; i++) {
scanf("%s %d", names[i], &happy);
int u = getId(names[i]);
hap[u] = happy;
}
ed = getId("ROM");
char x[50], y[50];
int u, v, cost;
for(int i = 0; i < k; i++) {
scanf("%s%s%d", x, y, &cost);
u = getId(x), v = getId(y);
//printf("%d %d\n", u, v);
addEdge(u, v, cost);
addEdge(v, u, cost);
}
dijkstra(0);
printf("%d %d %d %d\n", routes[ed], d[ed], hp[ed], (int)(hp[ed]/pt[ed]));
print(ed);
printf("\n");
}
return 0;
}
如有不当之处欢迎指出!