萌新求助大佬 开了 long long还WA

P1342 请柬

文武武智障 @ 2018-08-08 10:22:03

#include<bits/stdc++.h>
using namespace std;
long long head1[1000010],head2[1000010];
long long n,m,num_edge1,num_edge2,ans;
struct Edge
{
    long long next;
    long long to;
    long long dis;
}edge1[1000010],edge2[1000010];
inline int read()
{
    register long long x=0,w=0;char ch=0;
    while(!(ch>='0'&&ch<='9'))
    {
        if(ch=='-') w=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return w?-x:x;
}
inline void add_edge(int from,int to,long long dis)
{
    edge1[++num_edge1].next=head1[from];
    edge1[num_edge1].to=to;
    edge1[num_edge1].dis=dis;
    head1[from]=num_edge1;
    edge2[++num_edge2].next=head2[to];
    edge2[num_edge2].to=from;
    edge2[num_edge2].dis=dis;
    head2[to]=num_edge2;
}
long long d[1000010];
bool v[1000010];
inline void SPFA1()
{
    memset(d,0x3f3f3f3f,sizeof(d));
    memset(v,0,sizeof(v));
    priority_queue<pair<long long,int> > q;
    d[1]=0;
    q.push(make_pair(0,1));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        v[x]=0;
        for(register int i=head1[x];i;i=edge1[i].next)
        {
            long long y=edge1[i].to,z=edge1[i].dis;
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                if(!v[y]) { q.push(make_pair(-d[y],y)); v[y]=1; }
            }
        }
    }
    for(int i=1;i<=n;i++)
      ans+=d[i];
}
inline void SPFA2()
{
    memset(d,0x3f3f3f3f,sizeof(d));
    memset(v,0,sizeof(v));
    priority_queue<pair<long long,long long> > q;
    d[1]=0;
    q.push(make_pair(0,1));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        v[x]=0;
        for(register int i=head2[x];i;i=edge2[i].next)
        {
            long long y=edge2[i].to,z=edge2[i].dis;
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                if(!v[y]) { q.push(make_pair(-d[y],y)); v[y]=1; }
            }
        }
    }
    for(register int i=1;i<=n;i++)
      ans+=d[i];
}
int main(){
    cin>>n>>m;
    for(register int i=1;i<=m;i++)
    {
        long long x,y,d;
        x=read();
        y=read();
        d=read();
        add_edge(x,y,d);
    }
    SPFA1();
    SPFA2();
    printf("%d",ans);
}

by 文武武智障 @ 2018-08-08 11:23:31

**

我printf long long用的是%d

zz了


上一页 |