1133. Splitting A Linked List (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1133

大概描述:

对一串数,进行粗排序,排序规则,在保持原有顺序的前提下,将负数排在前列,将大于K排在后面

特征词:

链表

使用语言:

C++

解题思想:

再将链表存储好了之后,可以用依据链表元素值,对地址进行操作

题目得分:

22

提交次数:

2

时间

60分钟

代码

//柳神的想法果然强
#include<cstdio>
#include<vector>
using namespace std;
const int MAXI = 100000;
vector<int> w1,w2,w3;
int m[MAXI][2];

int main(){
 int i = 0;
 int num,fir,k;
 int a,b,c;
 scanf("%d %d %d",&fir,&num,&k);
 for(i = 0;i < num;i++) {
 scanf("%d %d %d",&a,&b,&c);
 m[a][0] = b;
 m[a][1] = c;
 }
 printf("read finished\n");
int r = fir;
 while(r != -1){
 if(m[r][0] < 0){
 w1.push_back(r);
 }
 if(m[r][0] > k){
 w3.push_back(r);
 }
 if(m[r][0] <= k&& m[r][0] >= 0){
 w2.push_back(r);
 }
 r = m[r][1];
 }
 int k1 = w1.size();
 for(i = 0 ;i < k1;i++){
 if(i == 0)
 printf("%05d %d ",w1[i],m[w1[i]][0]);
 else
 printf("%05d\n%05d %d ",w1[i],w1[i],m[w1[i]][0]);
 }
 //printf("%04d\n",m[w1[i]][1]);
int k2 = w2.size();
 for(i = 0 ;i < k2;i++){
 if(i == 0)
 printf("%05d\n%05d %d ",w2[i],w2[i],m[w2[i]][0]);
 else
 printf("%05d\n%05d %d ",w2[i],w2[i],m[w2[i]][0]);
 }
 //printf("%04d\n",m[w2[i]][1]);
 int k3 = w3.size();
 if(k3 == 0){
 printf("-1");
 }else{
 for(i = 0 ;i < k3;i++){
 if(i == 0)
 printf("%05d\n%05d %d ",w3[i],w3[i],m[w3[i]][0]);
 else
 printf("%05d\n%05d %d ",w3[i],w3[i],m[w3[i]][0]);
 }
printf("-1");
 }
}

运行结果

22

 成长

对于链表,在存储好基本关系后,只需要对地址处理就可以了

1132. Cut Integer (20)

题目:

https://www.patest.cn/contests/pat-a-practise/1132

大概描述:

将一个数进行拆分,将拆开的数相乘,判断是否为原数的因数

特征词:

数的运算

使用语言:

C++

解题思想:

就是用longlong 型进行存储,然后判断出位数

题目得分:

20

提交次数:

2

时间

26分钟

代码

#include<cstdio>
//Long Long 在使用时要注意初始化为0,不然很容易高位不为0
long long a = 0;
long long b = 0;
int panduan(long long c){
 int i = 0;
 // printf("c = %ld",c);
 while(c != 0){
 i ++;
 c = c / 10;
 // printf("c = %ld\n",c);
 }
 //printf("weishu :%d\n",i);
 return i ;
}
void disb(long long c){
 int wei1 = panduan(c);
 int i = 0;
 long long m = 1;
 for(i = 0;i < wei1 / 2;i++){
 m *= 10;
 }
 //printf("m = %ld",m);
 a = c % m;
 b = c / m;
}

int main(){
 int i = 0;
 int num = 0;
 scanf("%d",&num);
 long long test = 0;
 for(i = 0;i < num;i++){
 scanf("%ld",&test);
 disb(test);
 if(a * b == 0){
 printf("No\n");
 }else
 if(test % (a * b) == 0){
 printf("Yes\n");
 }else{
 printf("No\n");
 }
 }

}

运行结果

20

 成长

第一次遇到浮点错误,是因为除数为0,导致的

1136. A Delayed Palindrome (20)

题目:

https://www.patest.cn/contests/pat-a-practise/1136

大概描述:

对字符串数进行回文判断,如果不是在10次转置相加中是否出现进行输出

特征词:

string

使用语言:

C++

解题思想:

主要分为两个部分进行循环和进行转置相加的处理

题目得分:

20

提交次数:

2

时间

64分钟

代码

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string ss;
string bb;
string kk;
void rever(string ss){
 int num = ss.size();
 int i = 0;
 for(i = 0;i < num;i++){
 bb[i] = ss[num - i -1];
 printf("%c",bb[i]);
 }
 bb[i] = '\0';
 printf("rever number :");
 cout << bb;
}
void addd(string a,string b){
 //printf("进行相加操作:");
 //cout << a << " + " << b;
 //printf("\n");
 int num1 = a.size();
 int i= 0;
 int jin = 0;
 /*for(i = num1 -1;i >= 0;i--){
 if(a[i] - '0' + b[i] - '0' + jin>= 10){
 jin = 1;
 kk[i + 1] = a[i] - '0' + b[i] - '0' + jin - 10 + '0';
 }
 else{
 kk[i + 1] = a[i] - '0' + b[i] - '0' + jin + '0';
 jin = 0;
 }
 }
 if(jin > 0){
 kk[0] = jin + '0';
 }*/
 for(i = 0;i < num1 ;i++){
 if(a[i] - '0' + b[i] - '0' + jin >= 10){
 kk += a[i] + b[i] - '0' + jin - 10;
 jin = 1;
 }
 if(a[i] - '0' + b[i] - '0' + jin < 10){
 kk += a[i] + b[i] - '0' + jin;
 jin = 0;
 }
 }
 if(jin > 0){
 kk += 1 + '0';
 }
 reverse(kk.begin(),kk.end());
 //printf("相加结束结果为");
 ///cout << kk;//是否需要再末尾添加\0
 //printf("\n");
}

int main(){
 cin >> ss;
 int i = 0;
 bb = ss;
 reverse(bb.begin(),bb.end());
 int time = 0;
 while(ss.compare(bb)){
 if(++time > 10)
 break;
 addd(ss,bb);
 cout << ss << " + " << bb << " = " << kk << "\n";
 ss = kk;
 kk.clear();
 bb = ss;
 reverse(bb.begin(),bb.end());
 }
 if(ss.compare(bb) == 0){
 cout << ss << " is a palindromic number.";
 }
 else{
 printf("Not found in 10 iterations.");
 }

}

运行结果

20

 成长

这一题中学习是使用了string 的 reverse的方法,能更加灵活的使用这些函数和符号如“+”,在进行进位相加的处理时,可以从后往前进行累加,在用“ +”进行连接然后进行转置处理

1138. Postorder Traversal (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1138

大概描述:

前序加中序求后序第一个值

特征词:

树的遍历

使用语言:

C++

解题思想:

主要是进行单项递归从而减少不必要的时间浪费,对于最终的解必然是中序遍历的第一个或者第二个

题目得分:

22

提交次数:

2

时间

64分钟

代码

#include<cstdio>
#include<vector>
using namespace std;
vector<int> pre,in;
void seekz(int pres,int pree,int ins,int ine){
 //printf("%d %d %d %d\n",pres,pree,ins,ine);
 int i = 0;
 if(ine == 0){
 printf("%d",in[0]);
 return ;
 }
 if(ine == -1){
 printf("%d",in[1]);
 return ;
 }
 while(pre[pres] != in[i])
 i++;
 seekz(pres + 1,pres + i,ins,i - 1);

}
int main(){
 int num;
 int a;
 scanf("%d",&num);
 int i = 0;
 for(;i < num;i++){
 scanf("%d",&a);
 pre.push_back(a);
 }
 for(i = 0;i < num;i++){
 scanf("%d",&a);
 in.push_back(a);
 }
 seekz(0,num - 1,0,num - 1);


}

运行结果

22

 成长

这一题使用的是中序遍历加前序求后序第一个主要注意时间,关于遍历主要记住函数名就能写出来

void seekz(int pres,int pree,int ins,int ine)

因为我发现我忘记了很多,有些地方需要加强

1139. First Contact (30)

题目:

https://www.patest.cn/contests/pat-a-practise/1139

大概描述:

找出A与B之间的连接的两个节点

特征词:

模拟 图

使用语言:

C++

解题思想:

利用邻接表建立出图,然后将A,B的同性朋友找出然后判断他们是否存在关系,需要注意A的朋友不能包含B,B的朋友不能包含A

题目得分:

26

提交次数:

3

时间

120分钟

代码

#include<cstdio>
#include<algorithm>
#include<vector>
const int MAXI = 100000;
using namespace std;
vector<int> link[MAXI];
vector<int> s1;
vector<int> s2;
int sex[MAXI] = {0};
int aa,bb;
int aas = 0,bbs = 0;
vector<int> yyy ;
void o(){
 //printf("%d1003\n\n",sex[1003]);
 int i = 0;
 int s = link[aa].size();
 s1.clear();
 s2.clear();
 for(i = 0;i < s;i++){
 //printf("添加可能人%d%d\n",sex[link[aa][i]] ,link[aa][i]);
 if(sex[link[aa][i]] == aas&&link[aa][i] != bb){
 //printf("添加没人%d\n",link[aa][i]);
 s1.push_back(link[aa][i]);
 }
 }
 // printf("\n");
 s = link[bb].size();
 for(i = 0;i < s;i++){
 //printf("添加可能人%d%d\n",sex[link[bb][i]] ,link[bb][i]);
 if(sex[link[bb][i]] == bbs&&link[bb][i] != aa){
 // printf("添加媒人%d\n",link[bb][i]);
 s2.push_back(link[bb][i]);
 }
 }
 //printf("双方媒人准备完毕\n");
 for(i = 0;i < s1.size();i++){
 //printf("%d ",s1[i]);
 }
 //printf("\n");
 for(i = 0;i < s2.size();i++){
 //printf("%d ",s2[i]);
 }

}
bool qq(int a,int b){
 return a < b;
}
int find1(int a,int b){
 int i = 0;
 for(i = 0;i < link[a].size();i++){
 if(link[a][i] == b){
 return 1;
 }
 }
 return 0;
}
void oo(){
 yyy.clear();
 int i = 0;
 int j = 0;
 int k = s1.size();
 int kk = s2.size();
 //printf("进行匹配\n");
 for(i = 0;i < k;i++){
 for(j = 0;j < kk;j++){
 if(find1(s1[i],s2[j]) == 1){
 yyy.push_back(s1[i]);
 yyy.push_back(s2[j]);
 // printf("%d %d\n",s1[i],s2[j]);
 }
 }
 }
}


int main(){
 int i = 0;
 int j = 0;
 int a,b;
 int pnum,lnum;
 scanf("%d %d",&pnum,&lnum);
 for(i = 0;i < lnum;i++){
 scanf("%d %d",&a,&b);
 if(a > 0){
 sex[a] = 1;
 }else{
 a = -a;
 sex[a] = 0;
 }
 if(b > 0){
 sex[b] = 1;
 }else{
 b = -b;
 sex[b] = 0;
 }
 //printf("%d%d %d%d\n",sex[a],a,sex[b],b);
 // printf("000k");
 link[a].push_back(b);
 //printf("llll");
 link[b].push_back(a);
 // printf("")
 //printf("999");
 }
 //printf("关系读取完毕\n");
 //printf("%d1003\n\n",sex[1003]);
 int qnum = 0;
 scanf("%d",&qnum);
 //printf("%d1003\n\n",sex[1003]);
 for(i = 0;i < qnum;i++){
 scanf("%d %d",&a,&b);
 //printf("%d1003\n\n",sex[1003]);
 if(a > 0){
 aa = a;
 aas = 1;
 }else{
 aa = -a;
 aas = 0;
 }
 if(b > 0){
 bb = b;
 bbs = 1;
 }else{
 bb = -b;
 bbs = 0;
 }
 //printf("问题读取完毕\n");
 //printf("%d1003\n\n",sex[1003]);
 o();
 sort(s1.begin(),s1.end(),qq);
 sort(s2.begin(),s2.end(),qq);
 //printf("排序完毕\n");
 oo();
 int u = yyy.size();
 printf("%d\n",u/2);
 for(j = 0;j < u/2;j++){
 printf("%04d %04d\n",yyy[j * 2],yyy[j * 2 + 1]);
 }
 }
}

运行结果

26

 成长

对vector进行排序需要 sort(n1[1].begin(),n1[1].end(),pp);

在涉及到正负号时,要能够记得对能0得思考从而选择较为完备得思路

 

1059. Prime Factors (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1059

大概描述:

给定一个数写出组成它的素数乘积

特征词:

质数  筛法

使用语言:

C++

解题思想:

素数筛法构建素数表

题目得分:

25

提交次数:

3

时间

50分钟

代码

#include<cstdio>
//假设只进行1000000以内的素数表的建立
const int MU = 500000;
const int MAXI = 500000;
bool flg[MAXI] = {0};
int p[2][MAXI];
int r = 0;
void prime_table(){
 int i = 0;
 int j = 0;
 for(i = 2;i < MU;i++){
 if(flg[i] == false){
 p[0][r++] = i;
 // printf("flg %d",i);
 for(j = i + i;j < MU;j += i){
 // printf("OOK");
 flg[j] = true;
 }
 }
 }
}
int main(){
int m = 0;
scanf("%d",&m);
prime_table();//建立了1000000以内的素数表
//printf("table is OK\n");
int i = 0;
if(m == 1){
 printf("1=1");
 return 0;
}
int k = m;
//printf("&&&&&&&&");
//printf("%d",r);
for(i = 0;i < r;i++){
 // printf("&&&&&&&&1\n");
 if(k == 1){
 // printf("&&&&&&&&2\n");
 break;
 }else{
 if(k % p[0][i] == 0){
 // printf("pp%d",p[0][i]);
 p[1][i] ++;
 k = k / p[0][i];
 i --;

 }
 }
}
int u = 0;
for(i = 0;i < r;i++){
 if(p[1][i] != 0){
 u++;
 }
}
if(k != 1){
 u++;
}
printf("%d=",m);
for(i = 0;i < r;i++){
 if(p[1][i] == 1){
 u --;
 printf("%d",p[0][i]);
 if(u != 0){
 printf("*");
 }
 }
 if(p[1][i] > 1){
 u --;
 printf("%d^%d",p[0][i],p[1][i]);
 if(u != 0){
 printf("*");
 }
 }
}
if(k != 1){
 printf("%d",k);
}
}

运行结果

25

 成长

这一题真算尽心思,其中最麻烦的部分就是在建立好素数表后,因为内存的限制所以只能建出500000以内的素数表,但是int中正数的最大值2147483647,那么对于所给的数组成它的素数一旦超出500000该怎么处理能,后来推导发现,在将给定的一个数让他输出小于500000的组成素数后,如果此时还有其他组成数,那么直接输出。例如

1000018 = 2 * 500009

那么对于在500000以内的素数因子,2会被输出而,500009则是直接被输出,为什么可以直接被输出,下面给出证明:

如果在经过500000以内因子输出后,还有其他因子a,那么这个因子a肯定是超过500000的一个数,而这个数a如果是素数那么就可以直接输出,如果这个数a并不是素数,那么组成的它的素数因子至少有两个且他们的值都大于500000,那么a的值至少为500000*500000 =250000000000 > 2147483647远远大于int 的范围因此是不可能的因此,如果存在a,那么一定是一个素数,可以直接输出。

这是我在得到了23分后想到代码可能存在的问题,思考良久,得到的可能测试点,在运行了一下后,还是23分怎么会呢,我已经想到了那么多。

突然,猛然惊悟,好像还有一个数忘了,1。

原来那个测试点并不是1000018,卧槽。

凌乱在风中…….

 

1096. Consecutive Factors (20)

题目:

https://www.patest.cn/contests/pat-a-practise/1096

大概描述:

给定一个数判断内部来连续最长质数

特征词:

质数

使用语言:

C++

解题思想:

两层循环用于判断该点及其后面的点

题目得分:

19

提交次数:

3

时间

50分钟

代码

#include<cstdio>
#include<cmath>
int main(){
 int num;
 scanf("%d",&num);
 int len = 0;
 int maxi = 0;
 int x = 0;
 int r = num;
 int i = 0,j = 0;
 for(i = 2;i < sqrt(num) + 1;i++){
 r = num;
 for(j = i;j < sqrt(num) + 1;j++){
 //printf("j = %d\n",j);
 if(r % j != 0){
 //printf("break %d",j);
 break;
 }
 if(r % j == 0){
 r = r / j;
 if(r == 0)
 break;
 }
 }
 len = j - i;
 //printf("\nlen = %d\n",len);
 if(maxi < len){
 maxi = len;
 x = i;
 }
 }

 printf("%d\n",maxi);
 for(i = 0;i < maxi;i++){
 printf("%d",x + i);
 if(i != maxi - 1)
 printf("*");
 }
}

运行结果

19

 成长

什么都不想说了,“风在吼,马在叫,黄河在咆哮……….”

1015. Reversible Primes (20)

题目:

https://www.patest.cn/contests/pat-a-practise/1015

大概描述:

给定一个数和一个进制,先判断该数是否是素数,在求这个数在该进制下的转置数的十进制是否是素数

特征词:

素数   进制

使用语言:

C++

解题思想:

判断素数加进制转化加转置

题目得分:

18

提交次数:

5

时间

50分钟

代码

#include<cstdio>
#include<cmath>
int pprime(int a){
 int i = 0;
 //printf("&&&&");
 for(i = 2;i < (sqrt(a) + 1);i++){
 // printf("^^^^");
 if(a % i == 0)
 return 0;
 }
 return 1;
}
int rett(int a,int ret){
 int i = 0;
 char s[20];
 while(a != 0){
 s[i++] = a % ret;
 a = a / ret;
 }
 int t = 1;
 int b = 0;
 i --;
 while(i >= 0){
 b += s[i] * t;
 t *= ret;
 i --;
 }
 //printf("%d\n",b);
 return b;
}
int main(){
 int a = 0;
 int ret ;
 do{
 scanf("%d",&a);
 if(a < 0)
 return 0;
 else
 scanf("%d",&ret);
 // printf("OK\n");
 if(a == 1||pprime(a) == 0){
 printf("No\n");
 }
 // printf("OKKK\n");
 else{
 if(pprime(rett(a,ret)) == 1)
 printf("Yes");
 else
 printf("No");
 printf("\n");
 }
 }while(1);

}

运行结果

18

 成长

什么都不想说了,“风在吼,马在叫…….”

1105. Spiral Matrix (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1105

大概描述:

将一串数按照从大到小的顺序存储到螺旋数组中

特征词:

模拟

使用语言:

C++

解题思想:

就是先定义一个二维数组,然后按照4类规则进行存储

题目得分:

21

提交次数:

5

时间

220分钟

代码

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXI = 10009;
const int MAXII = 109;
bool qq(int a,int b){
 return a > b;
}
int main(){
 int m[MAXI];
 int m1[MAXII][MAXII];
 int num;
 scanf("%d",&num);
 int i = 0;
 for(i = 0;i < num;i++){
 scanf("%d",&m[i]);
 }
 //intf("OK\n");
 int j = 0;
 for(i = 1;i <= (sqrt(num) + 1);i++){
 if(num %i == 0){
 j = i;
 }
 }
 int cos = j;
 int clu = num / j;
 // printf("da %d xiao%d\n",cos,clu);
 if(num == 2){
 cos = num / j;
 clu = j;
 }
 //建一个二维数组将值输入
 sort(m,m + num,qq);
 //printf("sort OK\n");
 j = 0;
 int u = 0;
 int k = clu;
 int r = cos;
 u = 0;
 i = 0;
int f = -1;
int cl = clu;
 int s = -1;
 while(j != num){

 for(i = ++f;i < cl&&j != num;i++){
 m1[u][i] = m[j++];
 // printf("%d !",m1[u][i]);
 }
 cl --;
 // printf("\n");
 i --;
 for(u++;u < r &&j != num;u++){
 m1[u][i] = m[j++];
 // printf("u[%d][%d]%d !",u,k,m1[u][k]);
 }
 k = i;
 //printf("\n");
 r --;
 u --;
 for(i = --k;i > s&&j != num;i--){
 m1[u][i] = m[j++];
 // printf("%d !",m1[u][i]);
 }
 //printf("\n");
 s ++;
 i ++;
 for(--u;u > f&&j != num;u --){
 m1[u][i] = m[j++];
 // printf("u[%d][%d] %d !",u,i,m1[u][i]);
 }
 //printf("\n");
 u ++;
 //printf("OOK\n");
 }
 //printf("OVER\n");
 for(i = 0;i < cos;i++){
 printf("%d",m1[i][0]);
 for(j = 1;j < clu;j++){
 printf(" %d",m1[i][j]);
 }
 printf("\n");
 }
}

运行结果

21

 成长

原本以为刷过了最短路径+深度优先接下来会简单点,看来我还是踏实练功吧

1087. All Roads Lead to Rome (30)

题目:

https://www.patest.cn/contests/pat-a-practise/1087

大概描述:

给出图要求找出从一点到达终点,最短路径,最大开心程度,所经过城市最少的路径

特征词:

图   最短路径  深度搜索

使用语言:

C++

解题思想:

采用得是Dijkstra的最短路径算法,和深度搜素,其中先是进行最短路径 的计算对于,有距离相同的不同路径的存储,我是开辟了一个vector<int>qian[MAXI]的结构,将当前节点的前驱节点,存储起来,建成一棵树,然后用深度搜素,选出层数最低的路径,其中关于第一个输出,就是最短路径的条数,我是用int y[MAXI]这个数组在搜索最短路径时,进行累乘处理的

题目得分:

30

提交次数:

2

时间

200分钟

代码

//对于不是连续的点,下次需要进行标号
//请特别注意不让之后修改会很花时间
//这一题的第一个选项要求输出的是距离最小的路径条数,而不是路径最小。快乐最多的条数,

#include<cstdio>
#include<map>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iostream>
const int MAXI = 300;
const int INF = 1000000000;
using namespace std;
map<string ,int>s;//除了了map,或者将字符串转化成数字,还可以建立对应的字符串数组,用于标记
map<int ,string>q;
int happ[MAXI];
int cnum,lnum;
int lian[MAXI][MAXI];
int shor[MAXI];
bool flg[MAXI];
vector<int> qian[MAXI];
int happy[MAXI];//最大的快乐
int y[MAXI];
void bijk(int st){
 fill(shor,shor + MAXI, INF);
 qian[st].push_back(-1);
 memset(flg,false,sizeof(flg));
 // memset(qian,-1,sizeof(qian));
 y[st] = 1;
 shor[st] = 0;
 happy[st] = 0;
 int i,k;
 for(k = 0;k < cnum;k++){
 int mini = INF;
 int u = -1;
 for(i = 0;i < cnum;i++){
 if(flg[i] == false && shor[i]!= INF ){
 if(shor[i] < mini){
 mini = shor[i];
 u = i;
 }
 }
 }

 //printf("选定的数为%d\n",u);
 if(u == -1)
 return;
 //printf("进行检测\n");
 for(i = 0;i < cnum;i++){
 // printf("%d ",y[i]);
 }
 flg[u] = true;
 //printf("\n接下来是对相关的数进行修改\n");
 for(i = 0;i < cnum;i++){
 if(lian[u][i] != INF && flg[i] == false){
 // printf("y[%d] = %d",i,y[i]);
 //printf("y[%d] = %d\n",i,y[i]);
 if(lian[u][i] +shor[u] < shor[i]){
 y[i] = y[u];
 shor[i] = lian[u][i] + shor[u];
 qian[i].clear();//建立树
 qian[i].push_back(u);
 happy[i] = happy[u] + happ[i];
 }else if(lian[u][i] + shor[u] == shor[i]){
 // printf("进行合并\n");
 y[i] = y[i] + y[u] ;
 // printf("y[%d] = %d",i,y[i]);
 if(happy[i] < happy[u] + happ[i]){
 qian[i].clear();//建立树
 qian[i].push_back(u);
 happy[i] = happy[u] + happ[i];
 }else if(happy[i] == happy[u] + happ[i])
 qian[i].push_back(u);

 //qian[i].push_back(u);
 }
 }
 }
 }
}
//int time = 1;
int ni = INF;//表示最短层
vector<int> mm;//用于存储路径
vector<int> nn;//用于临时存储
void treep(int st,int ceng){
 nn.push_back(st);
 int i,j;
 if(qian[st][0] == -1){
 if(ceng < ni){
 ni = ceng;
 mm.clear();

 for(i = 0;i < nn.size();i++){
 mm.push_back(nn[i]);
 }
 }
 return;
 }
// time *= qian[st].size() ;
 for(j = 0;j < qian[st].size();j++){
 treep(qian[st][j],ceng + 1);
 }
}

int main(){
 string ss;
 string st;
 scanf("%d %d",&cnum,&lnum);
 cin >> st;
 s[st] = 0;
 q[0] = st;
 int i , d;
 for(i = 1;i < cnum;i++){
 cin >> ss;
 cin >> d;
 s[ss] = i;
 q[i] = ss;
 happ[i] = d;
 }
 string sss;
 fill(lian[0],lian[0] + MAXI * MAXI,INF);
 for(i = 0;i < lnum;i++){
 cin >> ss >> sss >> d;
 lian[s[ss]][s[sss]] = d;
 lian[s[sss]][s[ss]] = d;
 }
 bijk(0);
 //printf("最大快乐为:%d\n",happy[s["ROM"]]);
 //printf("最短路径为: %d\n",shor[s["ROM"]]);
 //printf("建树完成,接下来打印树\n");
 i = s["ROM"];
 int j = 0;
 for(i = 0;i < cnum;i++){
 // printf("%d:",i);
 for(j = qian[i].size() - 1;j >= 0;j--){
 // printf("%d ",qian[i][j]);
 }
 // printf("\n");
 }
 //printf("接下来进行深度遍历,找出最短层数\n");
 treep(s["ROM"],1);
 //printf("遍历结束,接下来反向输出结果\n");
 //printf("最小层数为:%d",ni);
 //printf("\n最短路径为:");
 for(i = 0;i < mm.size();i++){
 // printf("%d ",mm[i]);
 }
 //printf("\n");
 int a;
 printf("%d %d %d %d\n",y[s["ROM"]],shor[s["ROM"]],happy[s["ROM"]],happy[s["ROM"]] / (mm.size() - 1));
 cout << q[0];
 for(i = mm.size() - 2;i >= 0;i--){
 a = mm[i];
 cout << "->"<<q[a];
 }
 //printf("\n");
}


运行结果

30

 成长

一眼千年,又浪费了不少时间,这次主要是,对于输出向的第一项的,最低开销路线数的计算,理解错了,以为是最低开销且最大开心时间的路线计算,浪费了不少时间,不过也有好的一面,再一次加深了对最短路径算法和深度优先搜索算法的使用学习,毕竟这个阶段是学习阶段,应当反复琢磨,花点时间也是很好的。

对于不是连续的点,下次需要进行标号