题目大意：每经过一个地方就要交出相应的货物作为过路费，问将一批货物从起点运到终点，最少需要携带多少货物？
题目分析：在每一站交的过路费由当前拥有的货物量来决定，所以，要以终点为源点，求一次单源最短路即可。注意，输出要求路径字典序最小。
代码如下：
# include<iostream>
# include<cstdio>
# include<queue>
# include<vector>
# include<cstring>
# include<algorithm>
using namespace std;
# define LL long long const LL INF=0x7fffffffffffffff;
struct Node
{
int u;
LL d;
Node(int _u,LL _d):u(_u),d(_d){}
bool operator < (const Node &a) const {
return d>a.d;
}
};
int vis[55],n,p,s,e,path[55];
LL dist[55];
vector<int>G[55]; LL get(LL d,int id)
{
if(id>25) return 1LL;
LL l=d,r=d/(19LL)*(20LL)+19,ans;
while(l<r){
LL m=l+(r-l)/2;
LL k=m-(m+(LL)19)/((LL)20);
if(k>=d){
r=m;
ans=r;
}else{
l=m+1;
ans=l;
}
}
return ans-d;
/*LL temp=d*20LL/19;
while(temp-(temp+19LL)/20LL<d) ++temp;
return temp-d;*/
} void dijkstra()
{
for(int i=0;i<52;++i) path[i]=i;
memset(vis,0,sizeof(vis));
priority_queue<Node>q;
fill(dist,dist+52,INF);
dist[e]=p;
q.push(Node(e,(LL)p));
while(!q.empty())
{
Node u=q.top();
q.pop();
if(vis[u.u]) continue;
vis[u.u]=1;
for(int i=0;i<G[u.u].size();++i){
int v=G[u.u][i];
LL w=get(u.d,u.u);
if(dist[v]>w+u.d){
dist[v]=w+u.d;
path[v]=u.u;
q.push(Node(v,dist[v]));
}else if(dist[v]==w+u.d&&path[v]>u.u){
path[v]=u.u;
q.push(Node(v,dist[v]));
}
}
}
} void print(int u)
{
char c;
if(u>25) c=u+'a'-26;
else c=u+'A';
if(path[u]==u){
if(u!=s)
printf("-");
printf("%c\n",c);
return ;
}
if(u==s){
printf("%c",c);
print(path[u]);
}else{
printf("-%c",c);
print(path[u]);
}
} int main()
{
int u,v,cas=0;
char a[2],b[2],S[2],E[2];
while(scanf("%d",&n)&&n!=-1)
{
for(int i=0;i<52;++i) G[i].clear();
for(int i=0;i<n;++i){
scanf("%s%s",a,b);
if(a[0]>='A'&&a[0]<='Z') u=a[0]-'A';
else u=a[0]-'a'+26;
if(b[0]>='A'&&b[0]<='Z') v=b[0]-'A';
else v=b[0]-'a'+26;
G[u].push_back(v);
G[v].push_back(u);
}
scanf("%d%s%s",&p,S,E);
if(S[0]>='A'&&S[0]<='Z') s=S[0]-'A';
else s=S[0]-'a'+26;
if(E[0]>='A'&&E[0]<='Z') e=E[0]-'A';
else e=E[0]-'a'+26; dijkstra(); printf("Case %d:\n",++cas);
printf("%lld\n",dist[s]);
print(s);
}
return 0;
}