求高手解答!做PAT甲级的1030题时出现内存超限的情况

这是我的代码

 #include<iostream>
#include<fstream>
#include<vector>
#define inf 9999999;
using namespace std;


int main()
{

//  ifstream file("da.txt");
//  file >> N >> M >> S >>D;
    int N,M,S,D;
    cin >>N >>M>>S>>D;
    int **map,**cost,*dis,*cos,*last,*book;
    map = new int*[N];
    cost = new int*[N];
    dis = new int[N];
    cos = new int[N];
    last = new int[N];
    book = new int[N];
    for(int i= 0; i<N; i++)
    {
        *(map+i) = new int[N];  
        *(cost+i) = new int[N];
    }
    for(int i=0; i<N; i++)
    {
        dis[i]=inf;
        cos[i]=0;
        last[i]=0;
        book[i]=0;
            for(int j=0; j<N; j++)
            {
                map[i][j]=0;
                cost[i][j]=0;
            }
    }

    int a, b,c,d;
    for(int i = 1; i<=M ;i++)
    {
    //  file >> a >> b >> c >> d;
        cin >> a >> b >> c >> d;
        map[a][b]=map[b][a] = c;
        cost[a][b]=cost[b][a] = d;
    }

    for(int i = 0; i<N; i++)
    {
        if(map[S][i]!=0){
            dis[i] = map[S][i];
            cos[i] = cost[S][i];
        }
    }
    int index;
    int mindis=inf;
    for(int k =1; k<N; k++)
    {
        for(int i =0 ;i<N; i++)
        {
            if(dis[i] && dis[i]<mindis && !book[i])
            {
                index = i;
                mindis = dis[i];
            }
        }
        book[index] = 1;
        mindis = inf;

        for(int j= 0; j<N; j++)
        {
            if(j!=S && dis[j]>=dis[index]+map[index][j] && map[index][j])
            {

                if(dis[j]==dis[index]+map[index][j] && cos[j] < cos[index]+cost[index][j])
                    continue;
                else 
                {
                    dis[j] = dis[index]+map[index][j];
                    last[j] = index;
                    cos[j] = cos[index]+cost[index][j];
                }
            }
        }
    }
    vector<int> line;
    int P =D;
    while(P!=S)
    {
        line.push_back(P);
        P = last[P];
    }
    cout << S <<" ";
    for(int i=line.size()-1; i>=0 ;i--)
        cout << line[i]<<" "; 
    cout << dis[D]<<" ";
    cout << cos[D];
}

我看能通过测试的答案和我差不多。。为啥我这个内存就超了?
感谢!

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
浙大PAT甲级-1030
图的搜索(与1003类似) -dfs #include #include using namespace std; int n,m,s,d,cnt=0; int Dist[500][500]={0}; int Cost[500][500]; int mdist=INT_MAX, mcost=INT_MAX; int path[500]; int mpath[500]; bool visi
浙大PAT甲级 1030
单源最短路径,可用dijkstra算法,只不过需要多设置一个数组minn[505]来表示从源点开始到达该点的最短费用。 AC代码: #include #include #include #include #include #include #define inf 10000000 using namespace std; struct node { int dis; int c
【Dijkstra】PAT甲级1003 最短路径、PAT 甲级1030 (Dijkstra+DFS记录路径)
1003 Emergency (25 分) As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams...
PAT乙级题 1030 python解答
1030. 完美数列(25)给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M &amp;lt;= m * p,则称这个数列是完美数列。现在给定参数p和一些正整数,请你从中选择尽可能多的数构成一个完美数列。输入格式:输入第一行给出两个正整数N和p,其中N(&amp;lt;= 105)是输入的正整数的个数,p(&amp;lt;= 109)是给定的参数。第二行给出N个正整数,每个数不超过109。输出...
PAT甲级 1029 Median(25 分)AC 解决内存超限
1029 Median(25 分) Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 9, ...
PAT甲级题集
1001 A+B Format (20)分题解链接 要点: 1002 A+B for Polynomials (25)分题解链接 要点: 1003 Emergency (25)分题解链接 要点: 1004 Counting Leaves (30)分题解链接 要点: 1005 Spell It Right (20)分题解链接...
pat 甲级题
to_string(a+b) 函数 1001 A+B Format (20 分)
【PAT甲级真题整理一】1001~1030
目录 1001 A+B Format(20)a+b,3个一组用“,”隔开 1002 A+B for Polynomials(25)多项式相加 1003 Emergency(25)dfs搜索 1004 Counting Leaves(30)dfs 1005 Spell It Right(20)数位求和 1006 Sign In and Sign Out(25)找最大最小值 1007 M...
为什么内存超限了,求高手解答(附代码)
PAT上的一道题目,链接:[b]https://www.patest.cn/contests/pat-b-practise/1084[/b]rn代码如下,最后一个测试点过不去,说是内存超限rnrnrnimport java.util.Scanner;rnpublic class Mainrn public static void main(String[] args)rn rn Scanner in = new Scanner(System.in);rn int d;rn int n;rn d = in.nextInt();rn n = in.nextInt();rn String s = "" + d;rn n = n - 1;rn while(n>0)rn s = change(s);rn n--;rn rn System.out.println(s);rn in.close();rn rn public static String change(String s)rn String temp = "";rn char ch;rn int count;rn int i=0;rn while(i
PAT 甲级 20 分题
1001 A+B Format (20) ok 1005 Spell It Right (20) ok 1008 Elevator (20) ok 1011 World Cup Betting (20) ok 1015 Reversible Primes (20) ok 1019 General Palindromic Number (20) ...
PAT甲级 20分题
1.PAT1005 20分 测试样例3结果为零;不要忘记考虑零的结果 #include &lt;iostream&gt; #include &lt;bits/stdc++.h&gt; using namespace std; string change[] = {"zero","one","two","three","four","five","six","seven","eight","...
PAT甲级1011题代码
PAT甲级第1011题,之前自己做的时候写的代码,正确通过,但是效率不保证
PAT甲级1008题(Elevator)
#include &amp;lt;stdio.h&amp;gt; #include &amp;lt;math.h&amp;gt; int main() { int N,i,j; int sum=0; int a[100]; scanf(&quot;%d&quot;,&amp;amp;N); sum+=5*N; for(i=0; i&amp;lt;N; i++) { scanf(&quot;%d&quot;,&amp;am...
PAT甲级刷题记录
从今天开始记录PAT甲级的代码啦 ~(๑‾ ꇴ ‾๑) 每天一两道~ 1001 - 字符串处理sstream 1002 - 模拟 1003 - 最短路的条数(好题) 1004 - 前向星+dfs 1005 - 模拟 1006 - 最大值最小值 1007 - 最大连续子序 1008 - 模拟 1009 - 模拟 1010 - 进制转换(有坑) 1011 - 模拟 1012 ...
内存超限pat一元多项式的乘法与加法运算
输入格式:rn输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。rnrn输出格式:rn输出分2行,分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。零多项式应输出0 0。rn这是我的程序rn[code=c]#includern#includerntypedef struct PloyNode *Ploynomial;rnstruct PloyNodernrn int coef;rn int expon;rn Ploynomial link;rn;rnvoid Attach(int c,int e,Ploynomial *pRear)rnrn Ploynomial P;rn P=(Ploynomial)malloc(sizeof(struct PloyNode));rn P->coef=c;rn P->expon=e;rn P->link=NULL;rn (*pRear)->link=P;rn *pRear=P;rnrnPloynomial ReadPloy()rnrn Ploynomial P,Rear,t;rn int c,e,N;rn scanf("%d",&N);rn P=(Ploynomial)malloc(sizeof(struct PloyNode));rn P->link=NULL;rn Rear=P;rn while(N--)rn rn scanf("%d %d",&c,&e);rn Attach(c,e,&Rear);rn rn t=P;rn P=P->link;rn free(t);rn return P;rnrnPloynomial Add(Ploynomial P1,Ploynomial P2)rnrn Ploynomial P,Rear,t1,t2;rn int sum;rn t1=P1;t2=P2;rn P=(Ploynomial)malloc(sizeof(struct PloyNode));rn P->link=NULL;rn Rear=P;rn while(t1&&t2)rn rn if(t1->expon==t2->expon)rn rn sum=t1->coef+t2->coef;rn if(sum)Attach(sum,t1->expon,&Rear);rn t1=t1->link;rn t2=t2->link;rn rn else if(t1->expon>t2->expon)rn Attach(t1->coef,t1->expon,&Rear);rn t1=t1->link;rn rn elsern Attach(t2->coef,t2->expon,&Rear);rn t2=t2->link;rn rn rn while(t1)rn Attach(t1->coef,t1->expon,&Rear);rn t1=t1->link;rn rn while(t2)rn Attach(t2->coef,t2->expon,&Rear);rn t2=t2->link;rn rn t2=P;P=P->link;free(t2);rn return P;rnrnPloynomial Mulit(Ploynomial P1,Ploynomial P2)rnrn Ploynomial P,Rear,t,t1,t2;rn int c,e;rn if(!P1||!P2)return NULL;rn t1=P1;t2=P2;rn P=(Ploynomial)malloc(sizeof(struct PloyNode));rn P->link=NULL;rn Rear=P;rn while(t2)rn rn Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);rn t2=t2->link;rn rn t1=t1->link;rn while(t1)rn rn t2=P2;Rear=P;rn while(t2)rn rn c=t1->coef*t2->coef;rn e=t1->expon+t2->expon;rn while(Rear->link&&Rear->link->expon>e)rn Rear=Rear->link;rn rn if(Rear->link&&Rear->link->expon==e)rn rn if(Rear->link->coef+c)rn rn Rear->link->coef+=c;rn rn elsern t=Rear->link;rn Rear->link=t->link;rn free(t);rn rn rn elsern t=(Ploynomial)malloc(sizeof(struct PloyNode));rn t->coef=c;rn t->expon=e;rn t->link=Rear->link;rn Rear->link=t;rn Rear=Rear->link;rn rn rn t1=t1->link;rn rn t2=P;rn P=P->link;rn free(t2);rn return P;rnrnvoid PrintPloy(Ploynomial P)rnrn int flag=0;rn if(!P)rn rn printf("0 0\n");rn return;rn rn while(P)rn rn if(!flag)flag=1;rn else printf(" ");rn printf("%d %d",P->coef,P->expon);rn P=P->link;rn rn printf("\n");rnrnint main()rnrn Ploynomial P1,P2,PP,PS;rn P1=ReadPloy();rn P2=ReadPloy();rn PP=Mulit(P1,P2);rn PrintPloy(PP);rn PS=Add(P1,P2);rn PrintPloy(PS);rn return 0;rnrn[/code]rn断点调试提示在乘法函数的这[code=c] elsern t=(Ploynomial)malloc(sizeof(struct PloyNode));rn t->coef=c;rn t->expon=e;rn t->link=Rear->link;rn Rear->link=t;rn Rear=Rear->link;rn [/code]
Pat乙级1030题—— 完美数列(Python)
注意 完美数列不一定要从给出的数列最小的一项开始,而是找尽可能的包含最多数的完美数列。 这个代码用python2实现会出现一个测试点超时,用python3没有问题。 代码如下 # -*- coding: UTF-8 -*- def perfectSequence(): N, q= map(int, input().split()) numList = sorted(...
PAT 甲级
人名直接用char na[9],不用string; string记得加.c_str() scanf比cout快很多 string s.lenth() sort 的比较函数返回值是bool,返回true不交换,与qsort相反 pow(x,y)用的时候前面加(int) 两层循环注意i j
PAT甲级
                                                   欢迎找茬                                                                                                            作者 渣渣侠                         ...
[PAT]1030 完美数列
[PAT]1030 完美数列 题目链接: 1030 完美数列 解题思路: 本题有一点dp的思想,首先对输入数据从小到大排序,本来想套三层循环,最外面一层枚举最大完美数列长度,然后里面两层分别是完美数列的开头元素和结尾元素,仔细想了一下发现其实可以只用两层循环实现整个过程,首先定义最大长度maxnum=0,然后外层循环枚举数列的开头元素,内层循环枚举数列的结尾元素,如果长度大于maxnum,更新ma...
PAT 1030 完美数列
1030 完美数列(25 分) 给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M≤mp,则称这个数列是完美数列。 现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。 输入格式: 输入第一行给出两个正整数 N 和 p,其中 N(≤10​5​​)是输入的正整数的个数,p(≤10​9​​)是给定的参数。第二行给出 N 个正整数,每个数不...
PAT出现段错误情况
可能为数组越界,可以通过增加数组长度a[M]中的M尝试。
PAT程序设计考题——甲级1030(Travel Plan) C++实现
点击打开pat链接 #include #include #include #include #include #include #include #include #include using namespace std; #define INF 100000000 #define maxn 100010 struct highway{  int end;  int
PAT 1030完美数列
给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M 现在给定参数p和一些正整数,请你从中选择尽可能多的数构成一个完美数列。 输入格式: 输入第一行给出两个正整数N和p,其中N(5)是输入的正整数的个数,p(9)是给定的参数。第二行给出N个正整数,每个数不超过109。 输出格式: 在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
1030. Travel Plan (30) - Dijkstra
1030. Travel Plan (30)题目地址/* http://www.patest.cn/contests/pat-a-practise/1030 1030. Travel Plan (30) 此题用数组 把city结构体分开用变量 一直是内存超限??换成vector 加结构体的模式 就ok 了 另外 vector 使用resize() assign() 要会 */ #include <i
PAT甲级(advanced level)题目解答记录
目录 1001.A+B Format 1002.A+B for Polynomials 1003.Emergency 1020.Tree Traversals 1030.Travel Plan 1001.A+B Format 题目概述: 计算两个数字之和,输出时表示为每隔3位以逗号分隔的“标准形式”。 解题思路: 首先考虑int的取值范围。int一般为4个字节,即32位,能表示...
PAT 1030 完美数列
1030 完美数列(25)(25 分) 给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M&amp;lt;=m∗pM&amp;lt;=m∗pM 10510510^{5})是输入的正整数的个数,p(&amp;lt;= 10910910^{9})是给定的参数。第二行给出N个正整数,每个数不超过10910910^{9}。 输出格式: 在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。 ...
PAT乙级——1030(数组操作)
题目:完美数列 (25 分) 给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M≤mp,则称这个数列是完美数列。 现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。 输入格式: 输入第一行给出两个正整数 N 和 p,其中 N(≤10​5​​ )是输入的正整数的个数,p(≤10​9​​ )是给定的参数。第二行给出 N 个正整数,每个数不超过 ...
PAT乙级—1030
1030. 完美数列(25)时间限制300 ms内存限制65536 kB代码长度限制8000 B判题程序Standard作者CAO, Peng给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M &amp;lt;= m * p,则称这个数列是完美数列。现在给定参数p和一些正整数,请你从中选择尽可能多的数构成一个完美数列。输入格式:输入第一行给出两个正整数N和p,其中N(&amp;lt;= ...
【note】PAT甲级题目中的单词整理
randomize 使…随机化collaborate 合作gamblers 赌徒inadequate 不充分的shuffles 洗牌casino 赌场simulate 假装,模拟,模仿a deck of playing cards 一副牌Joker 鬼牌红桃(Heart)、黑桃(Spade)、方片(Diamond)、梅花(Club)trophy 奖牌,奖杯Lo
从PAT甲级1047题说开去
动态数组,流处理,超时,段错误
从PAT甲级1064题说开去
原题链接:https://www.patest.cn/contests/pat-a-practise/1064
PAT甲级题考点(转载各个大佬)
感谢各位大佬 嘻嘻 还有自己推下自己的写题过程和考前复习。。。虽然不咋地。。。不过复习完会很有底气 题集。。有一点不会是转载巨巨们的 https://blog.csdn.net/galesaur_wcy/article/details/83474880 还有这个是本人复习过程和考完感想 https://blog.csdn.net/galesaur_wcy/article/details/82...
【note】PAT甲级刷题笔记
例如扑克牌1~13,14~26,这样分类的数字,num / 13要考虑当num == 13的时候其实还是在第一个类别里面,但却由0变成了1。解决办法是:num = num - 1后,再进行num % 13,这样使得num变成了0~12,13~25,…正好符合除以得到的结果分类。但在num % 13 的时候,不需要先num = num - 1。需要的是num % 13 + 1,因为取余得到的结果是0~
关于pat甲级链表题的总结
1.链表类型题 输入一般 是起始结点的地址,与结点的个数n 然后n行都是 地址,数据 , 下一个结点的地址, 下一个地址连接点可能会发生改变, 但原结点地址一般不会改变 可以选择结构体方式存储, 或者分开(next[maxsize], data[maxsize]), 2. 设定一个 b数组存放满足题意要求结点的地址 3. 输出格式一般是 %05d %d %05d (结点的地址, 结...
深度优先搜索解最短路径------PAT甲级1003题
        /*此处应贴出PAT甲级1003题目地址 不过PAT官网最近在维护*/        先讨论一般情况下的深度优先搜索求解最短路径。其实就是借助DFS的思想穷举所有从起点到终点的路径,当找到一条路径后进行判断,如果满足我们希望找到的路径,则返回。如果当前访问的点不是终点,就遍历以该点为起点时能到达的点,如果这个能到达的点不在当前路径上,则递归走这个点。在不停的递归中我们需要一种数据结...
PAT甲级139题——完结撒花
突然想起来因为CSDN博客每日发文限制,今天刷的一些没发出来,现在想起来。。。 合影留念、、、虽然没啥用。。。。对于以后来说、。。 全程都是自己撸的,,没有去看晴神的宝典。。。毕竟有强迫症,总觉得不自己想出来会很不舒服。。。。部分题目实在被测试点卡住时,会去参考一些博客的样例提示,不过大多时候还是得自己看自己那shi一样的代码去找问题。。。 哎, 如果初试没过,那。。这也是第一次,也是最后一
PAT甲级20分的题总结
今天终于刷完了PAT甲级20分的题。下面总结一下。 20分的题没有涉及数据结构中图和树中的知识,也没有涉及到dp,基本上都是字符串、数位拆解、进制转化、分数求和、大数加减法,数学题这种基础的题目。前面的比较简单,后面个别题目有一定难度。 一定要熟练掌握STL中常用容器的用法,特别是map、vector、set。还要会用string中的常用函数,比如find(),substr(),stoi(),...
PAT甲级 1093 Count PAT's (25 分)逻辑题
参考链接:https://www.liuchuo.net/archives/1896 1093 Count PAT's (25 分) The string APPAPT contains two PAT's as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the se...
PAT——A1149(2018秋PAT甲级B题)
题目链接: 再一次认识到自己与别人的差距 明明结构体考试的时候自己也用了 但是没有想到可以应一个bool型数组来遍历 最后比较的时候逆向比较结构体数组就好了 #include&amp;lt;cstdio&amp;gt; #include&amp;lt;iostream&amp;gt; #include&amp;lt;cstring&amp;gt; #include&amp;lt;vector&amp;gt; #include&amp;lt;cmath&amp;gt...
PAT甲级--1093 Count PAT's(25 分)【逻辑题】
1093 Count PAT's(25 分) The string APPAPT contains two PAT's as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and t...
相关热词 c++和c#哪个就业率高 c# 批量动态创建控件 c# 模块和程序集的区别 c# gmap 截图 c# 验证码图片生成类 c# 再次尝试 连接失败 c#开发编写规范 c# 压缩图片好麻烦 c#计算数组中的平均值 c#获取路由参数