此题就是反向求最短路然后注意一个公式20
假设从a->b在a 时的距离值是q 则b是不阔能小于 x的其中x-(x/20)=q;注意（x/20)代表的是向上取整现在这就是x>=(20/19*q) 我们阔以认为x是(20/19*q)（然后(x/20)就是花费
这样的话会节省不少讨论呢。。。。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
struct diann
{
int value;
int num;
diann()
{
}
};
ll dist[5000], pre[5000];
int hashh[5000];
int m;
diann dian[5000];
int diantot;
typedef pair < int, diann >p;
struct edgee
{
int to;
};
edgee edge[8000];
int first[5000], nextt[8000];
int edgetot = 0;
void addedge(int a, int b)
{
edge[edgetot].to = b;
nextt[edgetot] = first[a];
first[a] = edgetot;
edgetot++;
edge[edgetot].to = a;
nextt[edgetot] = first[b];
first[b] = edgetot;
edgetot++;
}
struct com
{
bool operator()(p a, p b)
{
return a.first>b.first;
}
};
void distra(diann num,int tot,int begin,int end,int times)
{
for (int i = 0; i < tot; i++)dist[i] = 4611686018427387904, pre[i] = -1;
dist[num.num] = begin;
priority_queue<p, vector<p>, com>que;
que.push(p(begin, num));
while (!que.empty())
{
int num = que.top().second.num; int costkind = que.top().second.value<='Z'?1:0;
ll value = costkind ? ceil(ceil(dist[num] *1.0*20/19.0)*1.0/20) :1;
p temp = que.top();
que.pop();
if (dist[num] < temp.first)continue;
for (int i = first[num]; i != -1; i = nextt[i])
{
int now = edge[i].to;
if (dist[now] > dist[num] + value)
{
dist[now] = dist[num] + value;
pre[now] = num;
que.push(p(dist[now], dian[now]));
}
if (dist[now] == dist[num] + value&&dian[pre[now]].value > dian[num].value)
pre[now] = num;
}
}
printf("Case %d:\n", times);
printf("%lld\n", dist[hashh[end]]);
for (int i = hashh[end];i!=-1; i = pre[i])
{
if (pre[i] != -1)
printf("%c-", dian[i].value);
else
printf("%c", dian[i].value);
}
printf("\n");
}
int main()
{
//for (ll i = 1, kk = 0; kk <= 62; i = i * 2, kk++)
//cout << i << endl;
int k = 1;
while (scanf("%d", &m) && m != -1)
{
diantot = 0;
edgetot = 0;
for (int i = 0; i < 5000; i++)first[i] = -1,hashh[i]=-1;
getchar();
for (int i = 0; i < m; i++)
{
char a, b;
scanf("%c", &a);
getchar();
scanf("%c", &b);
getchar();
if(hashh[a]==-1)hashh[a] = diantot++,dian[hashh[a]].num = hashh[a], dian[hashh[a]].value = a;
if(hashh[b]==-1)hashh[b] = diantot++, dian[hashh[b]].num = hashh[b], dian[hashh[b]].value = b;
addedge(hashh[a], hashh[b]);
}
int d;
scanf("%d", &d);
getchar();
char a, b;
scanf("%c", &a);
getchar();
scanf("%c", &b);
if (m == 0)
{
printf("Case %d:\n", k);
printf("%d\n", d);
printf("%c\n", a);
k++;
continue;
}
distra(dian[hashh[b]], diantot, d, a, k);
k++;
}
}
