题目：The Toll! Revisited

题意：给一张由A~Z和a~z构成的无向图，大写字母表示城镇，小写字母表示村庄。每运送20个物品（不足20个当20个）进入城镇需要交1个过路费，无论运送多少物品进入村庄都只需一个过路费。给出起点和终点，求到达终点时有p个物品，需要从起点运多少物品。（进入终点要交费，进入起点不用交费）

思路：dijkstra求最短路。

代码：

#include<bits/stdc++.h>
using namespace std;#define n 52
#define ll long longstruct Pair {ll x;ll y;Pair(ll xx=0,ll yy=0) {x=xx,y=yy;}bool operator < (const Pair& oth) const {return x>oth.x;}
};int m;
int s,e;vector<int> a[n+5];ll dist[n+5];int num;void init() {for(int i=0; i<n; i++) a[i].clear();
}void readc(int& x) {char y;while(~(y=getchar())&&!isalpha(y));if(y<'a') x=y-'A';else x=y-'a'+26;
}bool v(int x) {if(x<26) return true;return false;
}char findc(int x) {if(x<26) return (char)x+'A';else return (char)x-26+'a';
}void readin() {for(int i=1; i<=m; i++) {int x,y;readc(x),readc(y);a[x].push_back(y);a[y].push_back(x);}for(int i=0; i<n; i++) {sort(a[i].begin(),a[i].end());}scanf("%d",&num);readc(s),readc(e);
}ll gt2(ll x,ll y) {if(y==0) return x-1;return x-(x+19)/20;
}ll gt(ll x,ll y) {if(y==0) {return x+1;}ll z=x*20/19;while(gt2(z,y)<x) z++;return z;
}void dijkstra(int bg) {priority_queue<Pair> p;bool c[n+5]= {0};for(int i=0; i<n; i++) dist[i]=(1ll<<50);dist[bg]=num;p.push(Pair(gt(num,v(bg)),bg));
//	cout<<num<<endl;while(!p.empty()) {Pair x=p.top();p.pop();
//		printf("%lld %c %lld\n",x.x,findc(x.y),dist[x.y]);if(c[x.y]) continue;c[x.y]=true;for(int i=0; i<a[x.y].size(); i++) {if(dist[a[x.y][i]]>x.x) {dist[a[x.y][i]]=x.x;p.push(Pair(gt(dist[a[x.y][i]],v(a[x.y][i])),a[x.y][i]));
//				cout<<"  --  "<<findc(a[x.y][i])<<' '<<dist[a[x.y][i]]<<endl;}}}
//	printf("\n");
}void find(int x,vector<int>& ans) {while(x!=e) {ans.push_back(x);for(int i=0; i<a[x].size(); i++) {if(gt2(dist[x],v(a[x][i]))==dist[a[x][i]]) {x=a[x][i];break;}}}ans.push_back(x);
}void print(int& t) {t++;printf("Case %d:\n%lld\n",t,dist[s]);vector<int> ans;find(s,ans);printf("%c",findc(ans[0]));for(int i=1; i<ans.size(); i++) {printf("-%c",findc(ans[i]));}printf("\n");
}int main() {int t=0;while(~scanf("%d",&m)&&~m) {init();readin();if(s==e) printf("Case %d:\n%d\n%c\n",++t,num,findc(s));else {dijkstra(e);print(t);}}return 0;
}