# UVA10537 The Toll! Revisited（最短路）

## The Toll! Revisited

### Input

The input consists of several test cases. Each test case consists of two parts: the roadmap followed by the delivery details.
The first line of the roadmap contains an integer n, which is the number of roads in the map
(0 ≤ n). Each of the next n lines contains exactly two letters representing the two endpoints of a road.
A capital letter represents a town; a lower case letter represents a village. Roads can be traveled in either direction.
Following the roadmap is a single line for the delivery details. This line consists of three things: an integer p (0 < p < 1000000000) for the number of items that must be delivered, a letter for the starting place, and a letter for the place of delivery. The roadmap is always such that the items can be delivered.
The last test case is followed by a line containing the number ‘-1’.

### Output

The output consists of three lines for each test case. First line displays the case number, second line
shows the number of items required at the beginning of the journey and third line shows the path
according to the problem statement above. Actually, the path contains all the city/village names that
Sindbad sees along his journey. Two consecutive city/village names in the path are separated by a
hyphen.

### Sample Input

1
a Z
19 a Z
5
A D
D X
A b
b c
c X
39 A X
-1

### Sample Output

Case 1:
20
a-Z
Case 2:
44
A-b-c-X

### 链接

https://cn.vjudge.net/problem/UVA-10537

——小白书P332

### 代码

StatusAccepted
Length2538
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const long long inf = (1ll << 62);
const int maxn = 110;
const int maxm = 1010;
ll dist[maxn], D;
bool vis[maxn];
int n, pre[maxn];

struct Node
{
int v;
ll dis;
Node(int _v, ll _dis): v(_v), dis(_dis) {}
bool operator < (const Node & r) const
{
return dis > r.dis;
}
};

struct Edge
{
int to, cost;
Edge(int _to): to(_to) {}
Edge(int _to, int _cost): to(_to), cost(_cost) {}
};

vector <Edge> edge[maxn];

{
edge[u].push_back(Edge(v));
}

int char2int(char ch) // 字母转数字
{
return ch - 'A';
}

char int2char(int x) // 数字转字母
{
return char(x + 65);
}

ll Cost(int u) // 到达点u时下一个点v的花费
{
if (u < 26) // 大写字母-城镇
return dist[u] + (dist[u] + 18) / 19;
return dist[u] + 1; // 村庄
}

void dijkstra(int s)
{
for (int i = 0; i < maxn; ++i) // 点数，不为n
{
dist[i] = inf;
vis[i] = false;
pre[i] = -1;
}
dist[s] = D;
priority_queue <Node> Q;
Q.push(Node(s, dist[s]));
while (!Q.empty())
{
Node tmp = Q.top();
Q.pop();
int u = tmp.v;
if (vis[u])
continue;
vis[u] = true;
for (int i = 0; i < edge[u].size(); ++i)
{
int v = edge[u][i].to;
if (vis[v])
continue;
ll cost = Cost(u);
if (dist[v] > cost) // 更新到达v点所需要的最少货物
{
pre[v] = u; // 记录前驱节点
dist[v] = cost;
Q.push(Node(v, dist[v]));
}
else if (dist[v] == cost && u < pre[v]) // 相等时取字典序最小的
pre[v] = u;
}
}
}

int main()
{
int s, t, kase = 0;
char s1[2], s2[2];
while (scanf("%d", &n))
{
if (n == -1)
break;
for (int i = 0; i < maxn; ++i) // 注意点的范围
edge[i].clear();
for (int i = 1; i <= n; ++i)
{
scanf("%s%s", s1, s2);
}
scanf("%lld%s%s", &D, s1, s2);
s =  char2int(s1[0]), t = char2int(s2[0]);
dijkstra(t); // 从终点开始逆序求最短路
printf("Case %d:\n", ++kase);
printf("%lld\n", dist[s]);
while (pre[s] != -1) // 逆序输出
{
printf("%c-", int2char(s));
s = pre[s];
}
printf("%c\n", int2char(t));
}
return 0;
}

The end.
2018-08-24 星期五