大致题意：有两种节点，一种是大写字母，一种是小写字母。首先输入m条边，当经过小写字母时需要付一单位的过路费，当经过大写字母时，要付当前财务的1/20做过路费。问在起点最少需要带多少物品使到达终点时还有k个物品。当有多条符合条件的路径时输出字典序最小的一个。
思路：已知终点的权值，那么可以从终点向前推。求终点到起点的最短路径，然后按字典序打印路径。
比较难处理的是：向前推时前驱节点的权值计算。列个方程算算就可以了，主要时不能整除的情况。
计算前驱结点dis值的时候，同时记录(i,j)的边权值，这是打印路径的依据。
#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <stack>
#include <queue>
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxm = 1010;
const int maxn = 60;
struct node
{
int v,w;
int next;
}edge[maxm];
int m;
int pre[maxn],cnt;
int start,end;
LL dis[maxn],p;
int vis[maxn];
vector <int> ans;
void init()
{
cnt = 0;
memset(pre,-1,sizeof(pre));
for(int i = 0; i < maxm; i++)
edge[i].w = 0;
}
void add(int u, int v)
{
edge[cnt].v = v;
edge[cnt].next = pre[u];
pre[u] = cnt++;
}
void dijstra()
{
priority_queue <pair<LL,int>, vector<pair<LL,int> >, greater<pair<LL,int> > > que;
while(!que.empty()) que.pop();
memset(dis,INF,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[end] = p;
que.push(make_pair(dis[end],end));
while(!que.empty())
{
int u = que.top().second;
que.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = pre[u]; i != -1; i = edge[i].next) //松弛相邻节点
{
if(vis[edge[i].v]) continue;
int v = edge[i].v;
if(u < 26)
{
//计算前驱结点的权值，判断是否整除，若不整除，尝试加1继续判断
if(dis[u]%19 == 0)
{
if(dis[v] > dis[u]/19*20)
{
dis[v] = dis[u]/19*20;
edge[i].w = edge[i^1].w = dis[v]-dis[u];
que.push(make_pair(dis[v],v));
}
}
else if( (dis[u]+1)%19 )
{
if(dis[v] > (dis[u]+1)*20/19)
{
dis[v] = (dis[u]+1)*20/19;
edge[i].w = edge[i^1].w = dis[v]-dis[u];
que.push(make_pair(dis[v],v));
}
}
else
{
if(dis[v] > (dis[u]+1)*20/19-1 )
{
dis[v] = (dis[u]+1)*20/19-1;
edge[i].w = edge[i^1].w = dis[v]-dis[u];
que.push(make_pair(dis[v],v));
}
}
}
else
{
if(dis[v] > dis[u]+1)
{
dis[v] = dis[u]+1;
edge[i].w = edge[i^1].w = 1;
que.push(make_pair(dis[v],v));
}
}
}
}
}
void solve()
{
ans.clear();
int now;
now = start;
ans.push_back(now);
while(now != end)
{
int tmp = 1<<6;
for(int i = pre[now]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
//因为输出字典序最小的，所以求出满足dis[now] - dis[v] == edge[i].w中最小的v
if(dis[now] - dis[v] == edge[i].w && v < tmp)
{
tmp = v;
}
}
ans.push_back(tmp);
now = tmp;
}
printf("%c",ans[0]+‘A‘);
for(int i = 1; i < (int)ans.size(); i++)
printf("-%c",ans[i]+‘A‘);
printf("\n");
}
int main()
{
int item = 1;
char t1,t2;
while(~scanf("%d",&m))
{
if(m == -1) break;
init();
getchar();
for(int i = 0; i < m; i++)
{
scanf("%c %c",&t1,&t2);
getchar();
add(t1-‘A‘,t2-‘A‘);
add(t2-‘A‘,t1-‘A‘);
}
scanf("%lld %c %c",&p,&t1,&t2);
start = t1-‘A‘;
end = t2-‘A‘;
dijstra();
printf("Case %d:\n",item++);
printf("%lld\n",dis[start]);
solve();
}
return 0;
}