萌新求助,可持久化可并堆WA48pts

@柳苏明 2020-09-16 20:50 回复

检查过了快读没有锅,但是有几个点就是比标准输出小。求dalao帮助。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <utility>
#include <cmath>

namespace quick {
#define tp template<typename Type>
    namespace in {
        inline char getc() {
            static char buf[1<<21],*p1=buf,*p2=buf;
            return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
        }
        inline int read(char *s) {
            *s=getc();
            while(isspace(*s)) {*s=getc();if(*s==EOF) return 0;}
            while(!isspace(*s)&&*s!=EOF) {s++;*s=getc();}
            *s='\0'; return 1;
        }
        inline int read(double &x) {
            x=0;bool k=false;double d=1;char c=getc();
            while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
            while(isdigit(c)) {x=x*10+(c^48);c=getc();}
            if(c!='.') return 1;
            c=getc();
            while(isdigit(c)) {d/=10.0;x+=d*(c^48);c=getc();}
            x*=(k?-1.0:1.0); return 1;
        }
        tp inline int read(Type &x) {
            x=0;bool k=false;char c=getc();
            while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
            while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getc();}
            x*=(k?-1:1); return 1;
        }
        template <typename Type,typename... Args>
        inline int read(Type &t,Args &...args) {
            int res=0;
            res+=read(t);res+=read(args...);
            return res;
        }
    }
    using in::read;
    namespace out {
        char buf[1<<21];int p1=-1;const int p2=(1<<21)-1;
        inline void flush() {
            fwrite(buf,1,p1+1,stdout);
            p1=-1;
        }
        inline void putc(const char &c) {
            if(p1==p2) flush();
            buf[++p1]=c;
        }
        inline void write(char *s) {
            while(*s!='\0') putc(*s),s++;
        }
        inline void write(const char *s) {
            while(*s!='\0') putc(*s),s++;
        }
        tp inline void write(Type x) {
            static char buf[30];int p=-1;
            if(x<0) {putc('-');x=-x;}
            if(x==0) putc('0');
            else for(;x;x/=10) buf[++p]=x%10+48;
            for(;p!=-1;p--) putc(buf[p]);
        }
        inline void write(const char &c) {putc(c);}
        template <typename Type,typename... Args>
        inline void write(Type t,Args ...args) {
            write(t);write(args...);
        }
    }
    using out::write;
    using out::flush;
    tp inline Type max(const Type &a,const Type &b) {
        if(a<b) return b;
        return a;
    }
    tp inline Type min(const Type &a,const Type &b) {
        if(a<b) return a;
        return b;
    }
    tp inline void swap(Type &a,Type &b) {
        a^=b^=a^=b;
    }
    tp inline Type abs(const Type &a) {
        return a>=0?a:-a;
    }
#undef tp
}
using namespace quick;

const int maxn=5000+10,maxm=200000+10;
int n,m;
double e;

struct Graph {
    struct Edge {
        int v,next;
        double w;
        Edge(const int &v,const int &next,const double &w)
            :v(v),next(next),w(w) {}
        Edge() {}
    }e[maxm];
    int head[maxn],cnt;
    inline int AddEdge(const int &u,const int &v,const double &w) {
        e[++cnt]=Edge(v,head[u],w);
        head[u]=cnt;
        return cnt;
    }
}g1,g2;
int id[maxm];
inline void AddEdge(const int &u,const int &v,const double &w) {
    id[g2.AddEdge(v,u,w)]=g1.AddEdge(u,v,w);
}

namespace LeftistTree {
#define lc(i) st[i].ch[0]
#define rc(i) st[i].ch[1]
    struct Node {
        double val;
        int ch[2],dist,v;//v记录出边
        Node(const double &val,const int &v) :val(val),v(v) {
            this->ch[0]=this->ch[1]=this->dist=0;
        }
        Node() {}
    }st[maxn<<8];
    int cnt;
    int Merge(int x,int y) {
        if(!x||!y) return x|y;
        if(st[x].val>st[y].val) swap(x,y);
        int cur=++cnt;
        st[cur]=st[x];
        rc(cur)=Merge(rc(cur),y);
        if(st[lc(cur)].dist<st[rc(cur)].dist) swap(lc(cur),rc(cur));
        st[cur].dist=st[rc(cur)].dist+1;
        return cur;
    }
    inline int Push(const int &x,const double &val,const int &v) {
        static int cur;
        st[cur=++cnt]=Node(val,v);
        return Merge(x,cur);
    }
#undef lc
#undef rc
}
using LeftistTree::st;
int root[maxn];

const double eps=1e-10;
inline int fcmp(const double &x) {
    if(fabs(x)<=eps) return 0;
    if(x>eps) return 1;
    return -1;
}

int s,t;
typedef std::pair<double,int> pii;
int fa[maxn],fae[maxn];
double d[maxn];
void Dijkstra(const int &s=::s,const int &t=::t) {
    static char vis[maxn];
    static std::priority_queue< pii, std::vector<pii>, std::greater<pii> > q;
    memset(d,0x43,sizeof d);
    memset(vis,0x0,sizeof vis);
    d[t]=0.0;
    q.push(std::make_pair(d[t],t));
    while(!q.empty()) {
        int u=q.top().second;
        q.pop();
        if(!~vis[u]) continue;
        vis[u]=0xff;
        for(int i(g2.head[u]);i;i=g2.e[i].next) {
            const int &v=g2.e[i].v;
            if(fcmp(d[v]-d[u]-g2.e[i].w)>0) {
                d[v]=d[u]+g2.e[i].w;
                q.push(std::make_pair(d[v],v));
                fa[v]=u;
                fae[v]=id[i];
            }
        }
    }
}

void Dfs(const int &u) {
    if(fa[u]) root[u]=root[fa[u]];
    for(int i(g1.head[u]);i;i=g1.e[i].next) {
        const int &v=g1.e[i].v;
        if(v==fa[u]) continue;
        root[u]=LeftistTree::Push(root[u],d[v]-d[u]+g1.e[i].w,v);
    }
    for(int i(g2.head[u]);i;i=g2.e[i].next) {
        const int &v=g2.e[i].v;
        if(fae[v]==id[i]) Dfs(v);
    }
}

int Solve() {
    Dijkstra();
    if(fcmp(e-d[s])<0) return 0;
    int ans=1;
    e-=d[s];
    Dfs(t);
    static std::priority_queue< pii, std::vector<pii>, std::greater<pii> > q;
    q.push(std::make_pair(d[s]+st[root[s]].val,root[s]));
    while(!q.empty()) {
        int u=q.top().second;
        double len=q.top().first;
        q.pop();
        if(fcmp(e-len)>=0) e-=len,ans++;
        else return ans;
        int v=root[st[u].v],lc=st[u].ch[0],rc=st[u].ch[1];
        if(v) q.push(std::make_pair(len+st[v].val,v));
        if(lc) q.push(std::make_pair(len-st[u].val+st[lc].val,lc));
        if(rc) q.push(std::make_pair(len-st[u].val+st[rc].val,rc));
    }
    return ans;
}

int main(void) {
#ifndef ONLINE_JUDGE
    freopen("kth.in","r",stdin);
#endif
    read(n,m,e);
    s=1,t=n;
    for(int i(1);i<=m;i++) {
        int u,v;double w;
        read(u,v,w);
        AddEdge(u,v,w);
    }
    write(Solve(),'\n');
    flush();
    return 0;
}
@_Wallace_  2020-09-17 21:03 回复 举报

@柳苏明 应该是因为你的 fa 存的是前驱点而不是前驱边,连接两个相同的点的边可能不知一条,但是你这样的话会吧所有的边都 ban 了,于是就漏数了。

解决方案就是让 fa 存边的编号。

本人十几分钟前还因为这个搞了半天

如果还有问题那就自己看看吧(

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。