第四届蓝桥杯 c/c++真题
《1》高斯日记
问题
大数学家高斯有个好习惯：无论如何都要记日记。
他的日记有个与众不同的地方，他从不注明年月日，而是用一个整数代替，比如：4210
后来人们知道，那个整数就是日期，它表示那一天是高斯出生后的第几天。这或许也是个好习惯，它时时刻刻提醒着主人：日子又过去一天，还有多少时光可以用于浪费呢？
高斯出生于：1777年4月30日。
在高斯发现的一个重要定理的日记上标注着：5343，因此可算出那天是：1791年12月15日。
高斯获得博士学位的那天日记上标着：8113
请你算出高斯获得博士学位的年月日。
提交答案的格式是：yyyy-mm-dd, 例如：1980-03-21
请严格按照格式，通过浏览器提交答案。
注意：只提交这个日期，不要写其它附加内容，比如：说明性的文字。
分析
这道题的关键是闰年的判断：若年份能被4整除且不能被100整除或年份能被400整除，则该年份为闰年。闰2月有29天，平年2月为28天。这里所给的测试数据为1791年12月15日，刚好是一个月的中旬，为了测试代码的正确性，最好加测试数据，可以用1791年12月14日，1791年12月16日，1791年12月1日，1791年12月30日等其他数据进行测试。
答案
1799-7-16
参考代码
/* 心得：其实这道题编程上并不难，就是闰年忘记怎么判断了。。。。 闰年：公元年数可被4整除为闰年,但是正百的年数必须是可以被400整除的才是闰年。其他都是平年=-= 闰年2月有29天，平年2月有28天 */ #include<stdio.h> #include<math.h> int date[]={0,31,29,31,30,31,30,31,31,30,31,30,31}; //闰年的判断 int f(int year) { if((year%4==0 && year%100!=0)||year%400==0) { return 29; } else { return 28; } } //1777年4月30日。 int main() { int n,i,j,d,m,y; scanf("%d",&n); y=1777; d=0; m=5; while(n>0) { if(m==13) { y++; m=1; } if(m==2) { i=f(y); n-=i; m++; } else { n-=date[m]; m++; } } if(n==0)printf("%d-%d-%d ",y,--m,d); else { m--; d+=date[m]-abs(n)-1; printf("%d-%d-%d ",y,m,d); } return 0; }
《2》 排它平方数
问题
小明正看着 203879 这个数字发呆。
原来，203879 * 203879 = 41566646641
这有什么神奇呢？仔细观察，203879 是个6位数，并且它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字。
具有这样特点的6位数还有一个，请你找出它！
再归纳一下筛选要求：
1. 6位正整数
2. 每个数位上的数字不同
3. 其平方数的每个数位不含原数字的任何组成数位
答案是一个6位的正整数。
请通过浏览器提交答案。
注意：只提交另一6位数，题中已经给出的这个不要提交。
注意：不要书写其它的内容（比如：说明性的文字）。
分析
可以利用一个标记素组x[9],x[i]=0表示数字i未被用过，否在被用过。利用标志数组，进行6位数既从100000到999999逐一遍历检查，即可选出符合条件的结果。
答案
639172
参考代码
/* 心得体会： 当数值很大的时候，整型数应该定义为long long (64bit)，这个倒是记得了，但是在进行平方运算的时候：n=(long long)i*i， 刚开始忘记了强制类型转换，结果运算完后等式右边i的类型为基准取结果，后来运算结果都是负数，结果才发现少了强制类型转换 在今后写程序的时候，应该特别小心，只要是等式两边的数据类型不一样的时候一定要记得显式的进行强制类型转换。此外在调用数学函数 进行相应计算的时候也应该注意这个问题，大多数数学函数都是以double型的数据为参数的，所以应该在传参数前进行类型转换。 */
#include<stdio.h> #include<string.h> int flag[10]; int f(long long n) { int i; while(n) { i=n%10; if(flag[i])return 0; else flag[i]=1; n/=10; } return 1; } int f2(long long n) { int i; while(n) { i=n%10; if(flag[i])return 0; n/=10; } return 1; } int main() { int i; long long n; for(i=102345;i<=987654;i++) { memset(flag,0,sizeof(flag));//要记得将flag数组清零 if(!f(i))continue; else { n=(long long)i*i;//结果要强制转换为long long型 if(f2(n)) { printf("%lld ",i); } } } return 0; }
《3》振兴中华
问题
小明参加了学校的趣味运动会，其中的一个项目是：跳格子。
地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg）
从我做起振
我做起振兴
做起振兴中
起振兴中华
比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。
要求跳过的路线刚好构成“从我做起振兴中华”这句话。
请你帮助小明算一算他一共有多少种可能的跳跃路线呢？
答案是一个整数，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。
从我做起振兴中华
分析
这题应该是用搜索算法解决，为了便于处理，可以将图中的文字映射成数字，对应关系为：
从我做起振兴中华
1 2 3 4 5 6 7 8
从我做起振
我做起振兴
做起振兴中
起振兴中华
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
题目即可以转换为求从1到8结束的情况。而每一步可以横向或纵向走到相邻的格子中，这个可以采用方向数组xy[][4]{{1,0},{-1,0},{0,1},{0,-1}}，每一次都尝试四个方向，若方向可行并且没有访问过，则可以转向下一个状态。此外使用标志数组flag[9],flag[1]~flag[8]分别标记已经通过的数字，visit[4][5]标志位置是否访问过。采用递归的方式进行遍历，知道flag完全标记则可以得到一种情况。
答案
35
参考代码
#include<stdio.h> #include<string.h> int table[][5]={{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8}},visit[4][6]; int t[][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组,t[][0]表示x（横向移动）,t[][1]表示y(纵向移动) int num,flag[10];
//当前x,y的位置，找下一步格子 void f(int x,int y) { int i; for(i=1;i<=8;i++)if(flag[i]==0)break; if(i>8)//得到从1到8的路径 { int j; /* for(i=0;i<4;i++) { for(j=0;j<6;j++) { printf("%d ",visit[i][j]); } printf(" "); } getchar();*/ num++; return; } int xn,yn; for(i=0;i<4;i++)//尝试四个方向 { xn=x+t[i][0]; yn=y+t[i][1]; if(visit[yn][xn]==0&&(xn>=0&&xn<5)&&(yn>=0&&yn<4)&&flag[table[yn][xn]]==0) {//如果格子没被访问过，并且x和y都合法，并且该数字没有走过 visit[yn][xn]=1; flag[table[yn][xn]]=1; f(xn,yn);//从当前格子[xn,yn]继续走 visit[yn][xn]=0; flag[table[yn][xn]]=0; } } } int main() { memset(visit,0,sizeof(visit)); num=0; visit[0][0]=1; flag[table[0][0]]=1; f(0,0);//起始点 printf("%d ",num); return 0; }
《4》颠倒的牌价
问题
小李的店里专卖其它店中下架的样品电视机，可称为：样品电视专卖店。
其标价都是4位数字（即千元不等）。
小李为了标价清晰、方便，使用了预制的类似数码管的标价签，只要用颜色笔涂数字就可以了（参见p1.jpg）。
这种价牌有个特点，对一些数字，倒过来看也是合理的数字。如：1 2 5 6 8 9 0 都可以。这样一来，如果牌子挂倒了，有可能完全变成了另一个价格，比如：1958 倒着挂就是：8561，差了几千元啊!!
当然，多数情况不能倒读，比如，1110 就不能倒过来，因为0不能作为开始数字。
有一天，悲剧终于发生了。某个店员不小心把店里的某两个价格牌给挂倒了。并且这两个价格牌的电视机都卖出去了!
庆幸的是价格出入不大，其中一个价牌赔了2百多，另一个价牌却赚了8百多，综合起来，反而多赚了558元。
请根据这些信息计算：赔钱的那个价牌正确的价格应该是多少？
答案是一个4位的整数，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。
分析
此题的第一步就是要先确定那些数字可以倒立有效，那些没有，int x[10];,x[i]表示数字i倒立后的数字，若倒立后无效则其值为-1，
显然：x[0]=0,x[1]=1,x[2]=2,x[3]=-1,x[4]=-1,x[5]=5,x[6]=9,x[7]=-1,x[8]=8,x[9]=6;
接下来第二步就是要出满足条件的牌号了，4位数，可以对1000~9999进行遍历，判断时再逐位拆分判断。
找出倒置前后差价为200-300 和800到900的牌子，然后综合利润为558，既可得出最后结果。此处还需要注意，题目要输出的是哪个牌价，可别写错了=.=。
答案
9088
参考代码
/* 心得体会：一定要认真审查题目，在做这道题的时候，起始已经对了，但是一直记错的要求，自己捏造，结果一直调试不出正确的结果 实际上是自己看错了题目，应该适当记录题目的关键字 */ #include<stdio.h> #include<math.h> int a[]={0,1,2,-1,-1,5,9,-1,8,6};//倒置数组 int b[4]; int f(int c) { int i,j=0,k=c; while(c) { i=c%10; b[j]=i; c/=10; j++; } // printf("%d to %d %d %d %d ",k,a[b[0]],a[b[1]],a[b[2]],a[b[3]]); if(b[0]==0)return 0; else if(a[b[0]]<0 || a[b[1]]<0 || a[b[2]]<0 || a[b[3]]<0)return 0; else return a[b[0]]*1000+a[b[1]]*100+a[b[2]]*10+a[b[3]]; } int main() { int n1,n2,d1,d2; int i,j; for(i=1000;i<10000;i++) { for(j=1000;j<10000;j++) { if((n1=f(i))==0 || (n2=f(j))==0)continue; d1=i-n1; d2=j-n2; if(d1*d2<0) { if(d1<0 && abs(d1)<300 && abs(d1)>200) { if(d2>0 && d2>800 && d2<900) { if(d2+d1==558) { printf("%d ",i);continue; } } } if(d2<0 && abs(d2)<300 && abs(d2)>200) { if(d1>0 && d1>800 && d1<900) { if(d2+d1==558) { printf("%d ",j);continue; } } } } } } return 0; }
《5》前缀判断
问题
题目标题：前缀判断
如下的代码判断 needle_start指向的串是否为haystack_start指向的串的前缀，如不是，则返回NULL。
比如："abcd1234" 就包含了 "abc" 为前缀
char* prefix(char* haystack_start, char* needle_start)
{
char* haystack = haystack_start;
char* needle = needle_start;
while(*haystack && *needle){
if(__________*(haystack++)!=*(needle++)_______) return NULL; //填空位置
}
if(*needle) return NULL;
return haystack_start;
}
请分析代码逻辑，并推测划线处的代码，通过网页提交。
注意：仅把缺少的代码作为答案，千万不要填写多余的代码、符号或说明文字！！
分析
这个题目的意思也就是，从两个串的开始进行对应位置的匹配，直到有一个串已经检查完则循环结束，期间若出现对应位置的字符不匹配则说明字符串不匹配提前结束循环返回。
《6》逆波兰表达式
问题
标题：逆波兰表达式
正常的表达式称为中缀表达式，运算符在中间，主要是给人阅读的，机器求解并不方便。
例如：3 + 5 * (2 + 6) - 1
而且，常常需要用括号来改变运算次序。
相反，如果使用逆波兰表达式（前缀表达式）表示，上面的算式则表示为：
- + 3 * 5 + 2 6 1
不再需要括号，机器可以用递归的方法很方便地求解。
为了简便，我们假设：
1. 只有 + - * 三种运算符
2. 每个运算数都是一个小于10的非负整数
下面的程序对一个逆波兰表示串进行求值。
其返回值为一个结构：其中第一元素表示求值结果，第二个元素表示它已解析的字符数。
struct EV
{
int result; //计算结果
int n; //消耗掉的字符数
};
struct EV evaluate(char* x)
{
struct EV ev = {0,0};
struct EV v1;
struct EV v2;
if(*x==0) return ev;
if(x[0]>='0' && x[0]<='9'){
ev.result = x[0]-'0';
ev.n = 1;
return ev;
}
v1 = evaluate(x+1);
v2 = evaluate(x+v1.n+1)_________; //填空位置
if(x[0]=='+') ev.result = v1.result + v2.result;
if(x[0]=='*') ev.result = v1.result * v2.result;
if(x[0]=='-') ev.result = v1.result - v2.result;
ev.n = 1+v1.n+v2.n;
return ev;
}
请分析代码逻辑，并推测划线处的代码，通过网页提交。
注意：仅把缺少的代码作为答案，千万不要填写多余的代码、符号或说明文字！！
分析
这道题考的是递归，struct EV evaluate(char* x),递归的参数是表达式字符串，返回值是EV结果，注意到EV结构的内容，可知返回的是“计算结果”和“消耗掉的字符数”。
读代码可以知道，每次调用函数的时候都会先检查当前字符x是否为数字，若为数字则将数字字符转换为int形数字，处理字符加1，并且数字返回。否则进行计算，那么就要找到进行运算的两个数字，
而需要天空的前一句语句为v1 = evaluate(x+1);显然是取当前符号左边的一组数字，返回的是计算结果，其中包含了处理过的字符个数，由此可知空缺代码应该为
evaluate(x+v1.n+1)，v1.n这个很关键，一定要注意跳过已经处理过的字符，从下一个未处理过的字符开始寻找第二组数据。最后进行计算。
审题的时候一定要搞清楚函数的输入和输出，但能更好的了解函数的功能。
《7》票据错误
问题
某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
要求程序首先输入一个整数N(N<100)表示后面数据行数。
接着读入N行数据。
每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000）
每个整数代表一个ID号。
要求程序输出1行，含两个整数m n，用空格分隔。
其中，m表示断号ID，n表示重号ID
例如：
用户输入：
2
5 6 8 11 9
10 12 9
则程序输出：
7 9
再例如：
用户输入：
6
164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
172 189 127 107 112 192 103 131 133 169 158
128 102 110 148 139 157 140 195 197
185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119
则程序输出：
105 120
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
分析
这题的解题思路很明确，既将所有的数据存到素组a[n]中，然后将其递增排序，若a[i+1]-a[i]==0则a[i]为重号的数字，若a[i+1]-a[i]==2则a[i]+1为缺失的号码。此题的难点主要在于如何准确接收所有的号码。可以使用scanf()的格式化输出，一直输入到输入结束。
参考代码
/* 心得体会： 这个程序调试了很多次都不通过，原因还是题目没有理解好。数据除了中间以空格隔开之外，末尾也是以空格加回车结束。 而起初考虑问题的时候只考虑了中间的空格，而没有考虑末尾的空格，导致程序一直不能通过。 此外要学会充分利用scanf()函数的格式化输入，函数返回成功输入的数据个数。 此外，再数据较多的时候采用重定向输入数据是非常方便的： freopen("错误票据data.txt","r",stdin); 不过需要注意的是，打开文件的函数再提交代码的时候一定要注释掉。 */ #include<stdio.h> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; #define M 100000 int n,a[M],b[M]; int main() { int i,j,d; char input[10]; // freopen("错误票据data.txt","r",stdin); char c; scanf("%d",&n); memset(a,0,sizeof(a)); j=-1; for(i=0;i<n;i++) { while(scanf("%d ",&d)==1)b[++j]=d; } sort(b,b+j+1); /* for(i=0;i<=j;i++) { printf("%d ",b[i]); } printf(" ");*/ int flag1=0,flag2=0,min=b[0],max=b[j],p,q; for(i=0;i<j&&(flag1==0||flag2==0);i++) { if(b[i+1]-b[i]==1)continue; if(flag1==0 && (b[i+1]-b[i])>1) { p=b[i]+1;flag1=1;continue; } if(flag2==0&&b[i+1]==b[i]) { q=b[i];flag2=1;continue; } } printf("%d %d",p,q); // fclose(f); return 0; }
《8》买不到的数目
问题
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入：
两个正整数，表示每种包装中糖的颗数(都不多于1000)
要求输出：
一个正整数，表示最大不能买到的糖数
不需要考虑无解的情况
例如：
用户输入：
4 7
程序应该输出：
17
再例如：
用户输入：
3 5
程序应该输出：
7
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 3000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
分析
形如ax+by=c的不定方程称为二元一次不定方程。显然
（1）a=0或b=0时，方程的解是确定的。
（2）c不是gcd(a,b)的倍数时，方程无解。
这里可以使用扩展欧几里得算法，也可以将上届定为a和b的最小公倍数，然后枚举求解。
参考代码
#include<stdio.h> //最大公约数 int gcb(int a,int b) { if(a%b==0)return b; else return gcb(b,a%b); } //最小公倍数 int gbs(int a,int b) { return a*b/gcb(a,b); } int buy(int m,int n) { int limi,i,j,k,flag,max; limi=gbs(m,n); for(i=limi;i>=1;i--) { flag=0; for(j=0;j<=limi/m;j++) { for(k=0;k<=limi/n;k++) { if((j!=0 || k!=0)&&(m*j+n*k)==i) { flag=1; break; } } if(flag==1)break; } if(flag==0)break; } return i; } int main() { int m,n; scanf("%d%d",&m,&n); printf("%d ",buy(m,n)); return 0; }
《9》剪格子
问题
如图p1.jpg所示，3 x 3 的格子中填写了一些整数。
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。
本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0
程序输入输出格式要求：
程序先读入两个整数 m n 用空格分割 (m,n<10)
表示表格的宽度和高度
接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000
程序输出：在所有解中，包含左上角的分割区可能包含的最小的格子数目。
例如：
用户输入：
3 3
10 1 52
20 30 1
1 2 3
则程序输出：
3
再例如：
用户输入：
4 3
1 1 1 1
1 30 80 2
1 1 1 100
则程序输出：
10
(参见p2.jpg)
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 5000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
分析
设所有格子的和为sum，显然sum%2==1的时候，显然无法分割。只有当sum%2==0的时候，才有可能将表格的和分为相等的两部分。此处使用搜索算法，其中要求的是“左上角”最少格子的分个区，所以可以以左上角的第一个格子为起点，定义方向数组a[][2]={{1,0},{-1,0},{0,1},{0,-1}},每次都尝试这四个方向，若可行则递归走下一步，直到得到结果或则所有可能都尝试完为止。
参考代码
#include<stdio.h> #include<string.h> int xy[][2]={{1,0},{0,1},{-1,0},{0,-1}};//下一步方向{x,y} int a[11][11],vis[11][11],sum,m,n;//m列n行 //检查{x，y}是否可行 int chack(int x,int y,int num) { if(x<1 ||x>n || y<1 || y>m) return 0; if((num+a[x][y])>sum) return 0; if(vis[x][y]) return 0; return 1; } int f1(int x,int y,int num)//遍历 { if(num==sum)return 1; int i,res=0,xn,yn; for(i=0;i<4;i++) { xn=x+xy[i][0]; yn=y+xy[i][1]; if(chack(xn,yn,num)) { vis[xn][yn]=1; int res=f1(xn,yn,num+a[xn][yn]); if(res>0)return res+1; vis[xn][yn]=0; } } return 0; } int main() { freopen("testin.txt","r+",stdin); scanf("%d%d",&m,&n); int i,j; sum = 0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&a[i][j]); sum+=a[i][j]; } } if(sum%2==1) printf("0 ");//如果所有格子的和不能分成相等的半 else { sum/=2; memset(vis,0,sizeof(vis));//从左上角开始遍历 vis[1][1]=1; printf("%d ",f1(1,1,a[1][1])); } return 0; }
《10》大臣的旅费
问题
很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。
聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。
J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入格式：
输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数
城市从1开始依次编号，1号城市为首都。
接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）
每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。
输出格式:
输出一个整数，表示大臣J最多花费的路费是多少。
样例输入:
5
1 2 2
1 3 1
2 4 5
2 5 4
样例输出:
135
样例说明:
大臣J从城市4到城市5要花费135的路费。
根据资源限制尽可能考虑支持更大的数据规模。
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 5000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
分析
这一道题的边比较稀疏，我用了邻接表存储图的结构，并且用distr求单元最短路径，保存最大值。遍历所有几点重复以上过程，最后再求出各组结果的最大值。不过最后得分为75,。
目前还没有想到别的比较好的解决方案。。。
参考代码
/* 超时，75分 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<queue> #include<algorithm> using namespace std; #define M 100000 #define inf 0 typedef struct node { int v,w; struct node *next; }Node; Node *head[M]; int visit[M],dist[M],money[M],vnum,resul[M]; void Buld() { memset(head,NULL,sizeof(head)); scanf("%d",&vnum); int u,v,w,i,j; Node *p; for(i=1;i<=vnum;i++) { scanf("%d%d%d",&u,&v,&w); p=(Node*)malloc(sizeof(Node)); p->v=v; p->w=w; p->next=head[u]; head[u]=p; p=(Node*)malloc(sizeof(Node)); p->v=u; p->w=w; p->next=head[v]; head[v]=p; } } int getmoney(int w1,int w2) { int i,sum=0; for(i=w1+1;i<=w2;i++) sum+=(i+10); return sum; } int getdisit(int s) { int i,j,u,v,w,m; memset(dist,0,sizeof(dist)); memset(money,0,sizeof(money)); memset(visit,0,sizeof(visit)); queue<int> Q; Node *p; Q.push(s); visit[s]=1; while(!Q.empty()) { u=Q.front(); Q.pop(); for(p=head[u];p!=NULL;p=p->next) { v=p->v; w=p->w; m=getmoney(dist[u],dist[u]+w); if((money[u]+m)>money[v]&&visit[v]==0) { dist[v]=dist[u]+w; money[v]=money[u]+m; Q.push(v); visit[v]=1; } } } sort(money+1,money+vnum+1); return money[vnum]; } int main() { // freopen("testin.txt","r",stdin); Buld(); int i,j,max=0,a; for(i=1;i<=vnum;i++) { a=getdisit(i); if(a>max)max=a; } printf("%d ",max); return 0; }