前者之所以叫加强版，就是把uva1027改编了，附加上打印路径罢了。
03年的final题哦！！虽然是水题，但不是我这个只会做图论题的跛子能轻易尝试的——因为有个数学坑。
题意：运送x个货物从a->b，沿途要上交过路费，village（小写字母）只需交一个单位的货物，town（大写字母）要交（x/20+((x%20==0)?0:1)）个单位的货物，即每20个货物要上交一个，不足的按20处理。现在已知要送到b点y个货物，那么最少从x出发要携带多少个货物。
注意：
1、路过town：19=20-1，同时19=21-2，所以要求最小值。
2、用dijkstra做，不过是从 b->a ，路径u->v的权值为经过u点扣除的货物。
3、打印路径：反向。从a->b，沿着d[v]==d[u]-s走，必为最短路。（从b->a有多条最短路，但从a->b沿着这个条件走，只有一条最短路）
4、字典序最小：预处理，sort（）后再建图。已知邻接表是模仿指针的头插法——后进先出。
5、数学坑= =:
先举个例子，要送到town A 10000个货物，针对10000，要扣除500。那么是不是携带10500就能满足要求呢？不是的T^T，10500-525==9975。所加上的500，仍然会被扣除一些货物。（TLE的原因，本以为差的不多，就每次做++判断了）
用递推直接求每部分要补充的货物，用大数据测发现差了1。这不是计算问题，而是存在错误的：沿用上一个例子，要送10000个货物，需扣除500个，500又需扣25个，那么25需不需要扣呢？扣的话又要扣2个，那么两个还要再扣一个么？？关键是余数，两次扣除的余数均不为0，那么分开算要扣2个，然而两数之和不足20，只需扣1个。
所以要直接求。
6、不要忘了long long，__int64 害我CE了一发
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std; const int MAXN=;
const LL INF =1e12+; struct Edge{
int v,next;
Edge(){}
Edge(int _v,int _next):v(_v),next(_next){}
}edge[MAXN*MAXN]; struct N{
int l,r;
}a[MAXN*MAXN]; int cmp(N a,N b)
{
if(a.l==b.l)
return a.r>b.r;
return a.l<b.l;
} int head[MAXN],tol;
int vis[MAXN];
LL d[MAXN];
queue<int>q; void init()
{
tol=;
memset(head,-,sizeof(head));
} void add(int u,int v)
{
edge[tol]=Edge(v,head[u]);
head[u]=tol++;
} void dijkstra(int st,int c)
{
memset(vis,,sizeof(vis));
for(int i=;i<;i++)
if(i==st)d[i]=c;
else d[i]=INF;
for(int i=;i<;i++)
{
if(head[i]==-)
continue; int x;
LL m=INF;
for(int j=;j<;j++)
{
if(!vis[j]&&d[j]<m){
x=j;
m=d[x];
}
}
vis[x]=;
LL t=,p=d[x];
if(x<)
while((p+t)-(p+t)/-((p+t)%==?:)<d[x])
{
t+=d[x]-((p+t)-(p+t)/-((p+t)%==?:));
}
else
t=;
for(int j=head[x];j!=-;j=edge[j].next)
{
int v=edge[j].v; if(d[v]>d[x]+t){
d[v]=d[x]+t;
}
}
}
} void road(int st,int ed)
{
int u=st;
LL s;
while(u!=ed)
{
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(v<)
s=d[u]/+((d[u]%==)?:);
else
s=;
if(d[v]==d[u]-s){
q.push(v);
u=v;
break;
}
}
}
while(!q.empty())
{
int v=q.front();q.pop();
if(v<)
printf("-%c",v+'A');
else
printf("-%c",v-+'a');
}
printf("\n");
} int num(char ch)
{
if('a'<=ch&&ch<='z')
return (+ch-'a');
else
return (ch-'A');
} int main()
{
int n,c,cnt=;
char str1[],str2[];
while(~scanf("%d",&n))
{
if(n==-)
return ;
init();
for(int i=;i<n;i++)
{
scanf("%s%s",str1,str2);
a[i].l=num(str1[]);
a[i].r=num(str2[]);
}
sort(a,a+n,cmp);
for(int i=;i<n;i++)
{
add(a[i].l,a[i].r);
add(a[i].r,a[i].l);
} scanf("%d%s%s",&c,str1,str2);
int x=num(str1[]);
int y=num(str2[]);
dijkstra(y,c); printf("Case %d:\n",cnt++);
printf("%lld\n",d[x]);
if(x<)
printf("%c",x+'A');
else
printf("%c",x-+'a');
road(x,y);
}
return ;
}
a b
b c
a d
d c
a c A B
B C
C D
D E
E F
F G
G H
H I
I J
J K
K L
L M
M N
N O
O P
P Q
Q R
R S
S T
T U
U V
V W
W X
X Y
Y Z
Z a
a b
b c
c d
d e
e f
f g
g h
h i
i j
j k
k l
l m
m n
n o
o p
p q
q r
r s
s t
t u
u v
v w
w x
x y
y z
A z A b
A B
b c
B c
A c A b
A B
b c
B c
A c A D
D X
A b
b c
c X
A X -
input
Case : a-b-c Case : A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-a-b-c-d-e-f-g-h-i-j-k-l-m-n-o-p-q-r-s-t-u-v-w-x-y-z Case : A-B-c Case : A-b-c Case : A-b-c-X
output
唉，吐槽一下。谁调试不用数据，就不能共享一下？做图论整天挨卡，想找个数据都找不到，自己又造不出好数据，要不然昨天那道lca就不会枚举344组数据了。当然，偶也知道debug的能力是重中之重，但这是经验积累起来的，以我这种弱菜，去刷uva&LA这种连题解都找不到的题库，受老咔哒了。难怪队友都说我整天愁眉苦脸的= =