题目来源：蓝皮书P331
·这道题使得我们更加深刻的去理解Dijkstra！
在做惯了if(dis[u]+w<dis[v])的普通最短路后，这道选择路径方案不是简单的比大小的题横在了我们的面前。
·英文题，述大意：
一个无向图，读入起点终点以及各条边的两个端点。读入load，要求从起点开始运输，能够向终点运送load个物品。节点分为两种：城镇节点会每20个单位的货物收取一个单位的货物作为过路费(注意23个货物会收2个单位的物品作为过路费)，乡村节点无论你带多少都只收取1个单位的货物。让你求出从起点出发最少携带多少货物，在经历层层苛刻收费后能够使到达终点的货物有load个(终点也要收费，起点不收费)。最后需要打印字典序最小的最优解路径。(n<=52,即大小写字母总个数，大写表示城镇，小写表示乡村)
·小小分析：
想办法调整最短路算法的路径选取策略。首先要保证最短路，但关键在于怎样计算到城镇的货物情况。由于不了解在起点带多少，却知道在终点剩多少，所以以终点为最短路源点，同样启用d[i]表示到达i点时至少要携带多少货物，使得走向终点后剩余货物保持为load个。
如果u是乡村，那就直接d[v]和d[u]+1比较即可。
如果u是城镇，那就值得思考：
考虑正常运输时，如果现在有k个货物，那么进入城市，则会变成多少个货物呢：rest=k-(k+19)/20[注意除号就是整除]。而现在由于最短路是倒推，所以我们只知道rest，要去求最小的k。必须保证均为正数，所以第一个不错而且容易考虑的方案就是二分。见下Dichotomy函数：
（x即上文的rest，mid即二分枚举的k）
·所以对于最短路的处理方式很简单，如果我们设节点：1~26为城镇,
27~52为乡村(这样便于字典序排序),在使用一个p[]来存前继结点，一切都变得美妙起来了：（图为Dijkstra部分）
最后进行一个倒序输出，就美妙至极了。
#include<stdio.h>
#include<queue>
#include<math.h>
#include<cstring>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define fo(i,a,x) for(int i=a[x],v=e[i].v;i>-1;i=e[i].next,v=e[i].v)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
using namespace std;const int N=102;struct E{int v,next;}e[N*N*2];
struct Q{int u;ll d;bool operator<(const Q& a)const{return d>a.d;}};
int ID(char u){int id;id='a'<=u&&u<='z'?u-'a'+27:u-'A'+1;return id;}
char DI(int u){char di;di=(1<=u&&u<=26)?'A'+u-1:'a'+u-27;return di;}
int n,head[N],k,t,S,T,p[N];ll inf=1,load,dis[N];bool vis[N];
void ADD(int u,int v){e[k]=(E){v,head[u]};head[u]=k++;}
ll dichotomy(ll x)
{
ll l=0,r=x*2+1,mid,res;
while(l<=r)mid=l+r>>1,mid-(mid+19)/20>=x?res=mid,r=mid-1:l=mid+1;
return res;
}
int main()
{
freopen("in.in","r",stdin);
go(i,1,14)inf*=10;while(scanf("%d",&n),++t,~n)
{
mem(head,-1);k=0;go(i,1,n)
{char u,v;scanf(" %c %c ",&u,&v);ADD(ID(u),ID(v));ADD(ID(v),ID(u));}
char a,b;scanf("%lld %c %c",&load,&a,&b);T=ID(a);S=ID(b); priority_queue<Q>q;mem(vis,0);
go(i,1,52)dis[i]=inf;p[S]=-1;
dis[S]=load;q.push((Q){S,dis[S]});
while(!q.empty())
{
Q x=q.top();q.pop();int u=x.u;if(vis[u])continue;vis[u]=1;
fo(i,head,u)
{
ll least=u<=26?dichotomy(dis[u]):dis[u]+1;
if(least<dis[v])dis[v]=least,p[v]=u,q.push((Q){v,dis[v]});
if(least==dis[v])u<p[v]?p[v]=u:1;
}
}
printf("Case %d:\n%lld\n",t,dis[T]);int u=T;printf("%c",DI(u));
while(p[u]>0)printf("-%c",DI(p[u])),u=p[u];printf("\n");
}
return 0;
}//Paul_Guderian
但还有一美妙之事需要提一提：
对于求城镇的least，有O(1)的方法。如果把你手中的货物20个20个地分组，那么可以分成这样：
那么如果你经过了一个城市，然后就变成了这样(20-1=19)：
·你肯定知道a<=20:那么可以美妙地变形：
a<=20
20a-19a<=20
20(a-1)<=19a
(a-1)*(20/19)<=a ————Paul
注意观察左边那一坨，是什么意思？
和上文一样，进城前是k，进城后是rest。那么：
上图中如果给图二中每一个数给它乘一个（20/19），那么：
所有的19全变成了20，a-1变成了(a-1)*(20/19)，此时的式子可以简写为：rest*(20/19)[你难道忘记了上文的rest和k?]
好的，仔细关注上文被”Paul”标记的不等式，我们豁然开朗：
rest*(20/19)<=k
要求k的最小值，就是左边的结果向上取整就可以了，即：
将上面程序中的least=dichotomy(…)改成：
代码其他地方没有变：
1 #include<stdio.h>
2 #include<queue>
3 #include<math.h>
4 #include<cstring>
5 #define go(i,a,b) for(int i=a;i<=b;i++)
6 #define fo(i,a,x) for(int i=a[x],v=e[i].v;i>-1;i=e[i].next,v=e[i].v)
7 #define mem(a,b) memset(a,b,sizeof(a))
8 #define ll long long
9 using namespace std;const int N=102;struct E{int v,next;}e[N*N*2];
10 struct Q{int u;ll d;bool operator<(const Q& a)const{return d>a.d;}};
11 int ID(char u){int id;id='a'<=u&&u<='z'?u-'a'+27:u-'A'+1;return id;}
12 char DI(int u){char di;di=(1<=u&&u<=26)?'A'+u-1:'a'+u-27;return di;}
13 int n,head[N],k,t,S,T,p[N];ll inf=1,load,dis[N];bool vis[N];
14 void ADD(int u,int v){e[k]=(E){v,head[u]};head[u]=k++;}
15 int main(){go(i,1,14)inf*=10;while(scanf("%d",&n),++t,~n)
16 {
17 mem(head,-1);k=0;go(i,1,n)
18 {char u,v;scanf(" %c %c ",&u,&v);ADD(ID(u),ID(v));ADD(ID(v),ID(u));}
19 char a,b;scanf("%lld %c %c",&load,&a,&b);T=ID(a);S=ID(b);
20 priority_queue<Q>q;mem(vis,0);go(i,1,52)dis[i]=inf;p[S]=-1;
21 dis[S]=load;q.push((Q){S,dis[S]});while(!q.empty())
22 {
23 Q x=q.top();q.pop();int u=x.u;if(vis[u])continue;vis[u]=1;
24 fo(i,head,u)
25 {
26 ll least=u<=26?(ll)ceil(dis[u]*1.0/19*20):dis[u]+1;
27 if(least<dis[v])dis[v]=least,p[v]=u,q.push((Q){v,dis[v]});
28 if(least==dis[v])u<p[v]?p[v]=u:1;
29 }
30 }
31 printf("Case %d:\n%lld\n",t,dis[T]);int u=T;printf("%c",DI(u));
32 while(p[u]>0)printf("-%c",DI(p[u])),u=p[u];printf("\n");
33 }return 0;}//Paul_Guderian
我们在未知的道路上行走，流着坚强的泪水放荡并且迷惘。————汪峰《觉醒》