UVA 10537 - The Toll! Revisited(dijstra扩张)

UVA 10537 - The Toll! Revisited

option=com_onlinejudge&Itemid=8&page=show_problem&category=550&problem=1478&mosmsg=Submission+received+with+ID+14135315" target="_blank" style="">题目链接

题意:给定一个无向图,大写字母是城市,小写字母是村庄,经过城市交过路费为当前货物的%5,路过村庄固定交1,给定起点终点和到目标地点要剩下的货物,问最少要带多少货物上路。并输出路径,假设有多种方案。要求字典序最小

思路:dijstra的逆向运用。d数组含义变成到该结点至少须要这么多货物,然后反向建图,从终点向起点反向做一遍

这题被坑了。。并非输出的城市才存在。比方以下这组例子

0

1 A A

应该输出

1

A

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
using namespace std; const int MAXNODE = 105; typedef long long Type;
const Type INF = (1LL<<61); struct Edge {
int u, v;
Type dist;
Edge() {}
Edge(int u, int v, Type dist) {
this->u = u;
this->v = v;
this->dist = dist;
}
}; struct HeapNode {
Type d;
int u;
HeapNode() {}
HeapNode(Type d, int u) {
this->d = d;
this->u = u;
}
bool operator < (const HeapNode& c) const {
return d > c.d;
}
}; char to[255]; struct Dijkstra {
int n, m;
vector<Edge> edges;
vector<int> g[MAXNODE];
bool done[MAXNODE];
Type d[MAXNODE];
int p[MAXNODE]; void init(int tot) {
n = tot;
for (int i = 0; i < n; i++)
g[i].clear();
edges.clear();
} void add_Edge(int u, int v, Type dist) {
edges.push_back(Edge(u, v, dist));
m = edges.size();
g[u].push_back(m - 1);
} void print(int e) {
if (p[e] == -1) {
printf("%c\n", to[e]);
return;
}
printf("%c-", to[e]);
print(edges[p[e]].u);
} void dijkstra(Type start, int s) {
priority_queue<HeapNode> Q;
for (int i = 0; i < n; i++) d[i] = INF;
d[s] = start;
p[s] = -1;
memset(done, false, sizeof(done));
Q.push(HeapNode(start, 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]];
Type need;
if (e.dist) need = (Type)ceil(d[u] * 1.0 / 19 * 20);
else need = d[u] + 1;
if (d[e.v] > need || (d[e.v] == need && to[u] < to[edges[p[e.v]].u])) {
d[e.v] = need;
p[e.v] = g[u][i];
Q.push(HeapNode(d[e.v], e.v));
}
}
}
}
} gao; typedef long long ll;
int n, m, vis[255]; int main() {
int cas = 0;
for (int i = 0; i < 26; i++) {
vis['A' + i] = i;
to[i] = 'A' + i;
}
for (int i = 0; i < 26; i++) {
vis['a' + i] = i + 26;
to[i + 26] = 'a' + i;
}
while (~scanf("%d", &m) && m != -1) {
gao.init(52);
char a[2], b[2];
int u, v;
while (m--) {
scanf("%s%s", a, b);
u = vis[a[0]], v = vis[b[0]];
gao.add_Edge(u, v, a[0] < 'a');
gao.add_Edge(v, u, b[0] < 'a');
}
ll need;
scanf("%lld%s%s", &need, a, b);
u = vis[a[0]]; v = vis[b[0]];
gao.dijkstra(need, v);
printf("Case %d:\n", ++cas);
printf("%lld\n", gao.d[u]);
gao.print(u);
}
return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

上一篇:项目在App Store的展示信息


下一篇:Linux - CentOS6.5服务器搭建与初始化配置详解(上)