请问各位大佬,为什么用了快读还是TLE,是否是方法出了问题

P1342 请柬

飘啊飘 @ 2020-05-21 11:52:22

#include<bits/stdc++.h>
using namespace std;
long long m,n,a,b,c,tot;
const long long u=1000005;
long long head[u],ver[u],net[u],edge[u],st[u],dist[u],head2[u],dist2[u],ans;
typedef pair <long long,long long> PII;
priority_queue <PII,vector<PII>,greater<PII> > q;

int read()
{
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}

void write(long long x)
{
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) 
        write(x/10);
    putchar(x%10+'0');
}

void add(long long a,long long b,long long c)
{
    net[++tot]=head[a];
    head[a]=tot;
    ver[tot]=b;
    edge[tot]=c;
}
void add2(long long a,long long b,long long c)
{
    net[++tot]=head2[a];
    head2[a]=tot;
    ver[tot]=b;
    edge[tot]=c;
}
void dijstla()
{
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    q.push({0,1});
    while(!q.empty())
    {
        PII temp=q.top();
        q.pop();
        long long dis=temp.first,v1=temp.second;
        if(st[v1]==1)
            continue;
        st[v1]=1;
        for(long long i=head[v1];i;i=net[i])
        {
            long long v=ver[i];
            if(dist[v]>dis+edge[i])
            {
                dist[v]=dis+edge[i];
                q.push({dist[v],v});
            }
        }
    }
    for(long long i=1;i<=n;++i)
        ans+=dist[i];
}
void dijstla2()
{
    memset(dist2,0x3f,sizeof(dist2));
    dist2[1]=0;
    q.push({0,1});
    while(!q.empty())
    {
        PII temp=q.top();
        q.pop();
        long long dis=temp.first,v1=temp.second;
        if(st[v1]==1)
            continue;
        st[v1]=1;
        for(long long i=head2[v1];i;i=net[i])
        {
            long long v=ver[i];
            if(dist2[v]>dis+edge[i])
            {
                dist2[v]=dis+edge[i];
                q.push({dist2[v],v});
            }
        }
    }
    for(long long i=1;i<=n;++i)
        ans+=dist2[i];
}

int main()
{
    n=read();
    m=read();
    for(long long i=1;i<=m;++i)
    {
        a=read();
        b=read();
        c=read();
        add(a,b,c);
        add2(b,a,c);
    }
    dijstla();
    memset(st,0,sizeof(st));
    dijstla2();
    write(ans);
    return 0;
}

by 飘啊飘 @ 2020-05-21 12:06:19

@HoneyLemon 那应该那些ll不能用呢


by XeCtera @ 2020-05-21 12:09:23

@飘啊飘 存最短路长度的都要开ll 别的都不用


by 飘啊飘 @ 2020-05-21 12:11:29

下课啦,我下周再来改吧,这周还要期中考试,我要复习


by the_hidden_corner @ 2020-05-21 12:19:40

@飘啊飘 IO优化全解


by the_hidden_corner @ 2020-05-21 12:21:28

@飘啊飘 直接用最后那个namespace封装的,调用写 read(n,m,(这里写其他变量,有几个就写几个));

put('(这里写输出格式,每个整数都空格就打个空格,换行就\n)',ans,这里写其他变量,就几个写几个);

调试需要Ctrl+Z


by 飘啊飘 @ 2020-05-26 14:43:12

@HoneyLemon @明日世界 此题已AC,谢谢各位大佬

const long long u=1000005;

只需要把u的值改成2000005就可以AC了

但我不知道为什么开小了会超时???


by the_hidden_corner @ 2020-05-26 14:54:58

@飘啊飘 哦,对了,有时候数组爆了出来的不是RE而是TLE...


by the_hidden_corner @ 2020-05-26 14:56:51

不过那里炸了呢..


by 飘啊飘 @ 2020-05-26 15:04:57

@明日世界 哦哦


by the_hidden_corner @ 2020-05-26 15:07:57

@飘啊飘 前两天蜜汁TLE然后不知道那里错了把所有的数组开到4倍TLE的一部分变成AC,剩下的变成MLE。。。。


上一页 | 下一页