UVA 10537 The Toll! Revisited uva1027 Toll（最短路+数学坑）

前者之所以叫加强版，就是把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了一发

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<vector>
  5 #include<algorithm>
  6 #define LL long long
  7 using namespace std;
  8 
  9 const int MAXN=55;
 10 const LL INF =1e12+1;
 11 
 12 struct Edge{
 13     int v,next;
 14     Edge(){}
 15     Edge(int _v,int _next):v(_v),next(_next){}
 16 }edge[MAXN*MAXN];
 17 
 18 struct N{
 19     int l,r;
 20 }a[MAXN*MAXN];
 21 
 22 int cmp(N a,N b)
 23 {
 24     if(a.l==b.l)
 25         return a.r>b.r;
 26     return a.l<b.l;
 27 }
 28 
 29 int head[MAXN],tol;
 30 int vis[MAXN];
 31 LL d[MAXN];
 32 queue<int>q;
 33 
 34 void init()
 35 {
 36     tol=0;
 37     memset(head,-1,sizeof(head));
 38 }
 39 
 40 void add(int u,int v)
 41 {
 42     edge[tol]=Edge(v,head[u]);
 43     head[u]=tol++;
 44 }
 45 
 46 void dijkstra(int st,int c)
 47 {
 48     memset(vis,0,sizeof(vis));
 49     for(int i=0;i<52;i++)
 50         if(i==st)d[i]=c;
 51         else d[i]=INF;
 52     for(int i=0;i<52;i++)
 53     {
 54         if(head[i]==-1)
 55             continue;
 56 
 57         int x;
 58         LL m=INF;
 59         for(int j=0;j<52;j++)
 60         {
 61             if(!vis[j]&&d[j]<m){
 62                 x=j;
 63                 m=d[x];
 64             }
 65         }
 66         vis[x]=1;
 67         LL t=0,p=d[x];
 68         if(x<26)
 69             while((p+t)-(p+t)/20-((p+t)%20==0?0:1)<d[x])
 70             {
 71                 t+=d[x]-((p+t)-(p+t)/20-((p+t)%20==0?0:1));
 72             }
 73         else
 74             t=1;
 75         for(int j=head[x];j!=-1;j=edge[j].next)
 76         {
 77             int v=edge[j].v;
 78 
 79             if(d[v]>d[x]+t){
 80                 d[v]=d[x]+t;
 81             }
 82         }
 83     }
 84 }
 85 
 86 void road(int st,int ed)
 87 {
 88     int u=st;
 89     LL s;
 90     while(u!=ed)
 91     {
 92         for(int i=head[u];i!=-1;i=edge[i].next)
 93         {
 94             int v=edge[i].v;
 95             if(v<26)
 96                 s=d[u]/20+((d[u]%20==0)?0:1);
 97             else
 98                 s=1;
 99             if(d[v]==d[u]-s){
100                 q.push(v);
101                 u=v;
102                 break;
103             }
104         }
105     }
106     while(!q.empty())
107     {
108         int v=q.front();q.pop();
109         if(v<26)
110             printf("-%c",v+'A');
111         else
112             printf("-%c",v-26+'a');
113     }
114     printf("
");
115 }
116 
117 int num(char ch)
118 {
119     if('a'<=ch&&ch<='z')
120         return (26+ch-'a');
121     else
122         return (ch-'A');
123 }
124 
125 int main()
126 {
127     int n,c,cnt=1;
128     char str1[2],str2[2];
129     while(~scanf("%d",&n))
130     {
131         if(n==-1)
132             return 0;
133         init();
134         for(int i=0;i<n;i++)
135         {
136             scanf("%s%s",str1,str2);
137             a[i].l=num(str1[0]);
138             a[i].r=num(str2[0]);
139         }
140         sort(a,a+n,cmp);
141         for(int i=0;i<n;i++)
142         {
143             add(a[i].l,a[i].r);
144             add(a[i].r,a[i].l);
145         }
146 
147         scanf("%d%s%s",&c,str1,str2);
148         int x=num(str1[0]);
149         int y=num(str2[0]);
150         dijkstra(y,c);
151 
152         printf("Case %d:
",cnt++);
153         printf("%lld
",d[x]);
154         if(x<26)
155             printf("%c",x+'A');
156         else
157             printf("%c",x-26+'a');
158         road(x,y);
159     }
160     return 0;
161 }

View Code

 1 4
 2 a b
 3 b c
 4 a d
 5 d c
 6 5 a c
 7 
 8 51
 9 A B
10 B C
11 C D
12 D E
13 E F
14 F G
15 G H
16 H I
17 I J
18 J K
19 K L
20 L M
21 M N
22 N O
23 O P
24 P Q
25 Q R
26 R S
27 S T
28 T U
29 U V
30 V W
31 W X
32 X Y
33 Y Z
34 Z a
35 a b
36 b c
37 c d
38 d e
39 e f
40 f g
41 g h
42 h i
43 i j
44 j k
45 k l
46 l m
47 m n
48 n o
49 o p
50 p q
51 q r
52 r s
53 s t
54 t u
55 u v
56 v w
57 w x
58 x y
59 y z
60 999999999 A z
61 
62 4
63 A b
64 A B
65 b c
66 B c
67 18 A c
68 
69 4
70 A b
71 A B
72 b c
73 B c
74 19 A c
75 
76 5
77 A D
78 D X
79 A b
80 b c
81 c X
82 39 A X
83 
84 -1

input

 1 Case 1:
 2 7
 3 a-b-c
 4 
 5 Case 2:
 6 3605038286
 7 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
 8 
 9 Case 3:
10 20
11 A-B-c
12 
13 Case 4:
14 21
15 A-b-c
16 
17 Case 5:
18 44
19 A-b-c-X

output

唉，吐槽一下。谁调试不用数据，就不能共享一下？做图论整天挨卡，想找个数据都找不到，自己又造不出好数据，要不然昨天那道lca就不会枚举344组数据了。当然，偶也知道debug的能力是重中之重，但这是经验积累起来的，以我这种弱菜，去刷uva&LA这种连题解都找不到的题库，受老咔哒了。难怪队友都说我整天愁眉苦脸的= =