wa求解

P1342 请柬

elpsconr @ 2024-04-08 22:29:31

为啥wa了,不知道问题出在哪里

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,idx,inx,res;
int h[N],e[N<<1],w[N<<1],ne[N<<1],d[N<<1];
int h1[N],e1[N<<1],w1[N<<1],ne1[N<<1],d1[N<<1];
bool st[N],st1[N];
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
void arcadd(int a,int b,int c)//反向建图
{
    e1[inx]=a;w1[inx]=c;ne1[inx]=h1[b];h1[b]=inx++;
}
void spfa1(int x)
{ 
    memset(d,0x3f,sizeof d);
    queue<int> q;
    st[x]=1;q.push(x);d[x]=0;
    while(!q.empty())
    {
        int ww=q.front();q.pop();
        for(int i=h[ww];~i;i=ne[i])
        {
            int j=e[i];
            if(d[j]>d[ww]+w[i])
            {
                d[j]=d[ww]+w[i];
                if(!st[j])
                {
                    q.push(j);st[j]=1;
                }
            }
        }
    }
    for(int i=2;i<=n;++i) res+=d[i];
}
void spfa2(int x)
{
    memset(d1,0x3f,sizeof d1);
    queue<int> q;
    q.push(x);d1[x]=0,st1[x]=1;
    while(!q.empty())
    {
        int ww=q.front();q.pop();
        for(int i=h1[ww];~i;i=ne1[i])
        {
            int j=e1[i];
            if(d1[j]>d1[ww]+w1[i])
            {
                d1[j]=d1[ww]+w1[i];
                if(!st1[j])
                {
                    q.push(j);st1[j]=1;
                }
            }
        }
    }
    for(int i=2;i<=n;++i) res+=d1[i];
}
int main()
{

  memset(h,-1,sizeof h);
  memset(h1,-1,sizeof h);
  cin>>n>>m;
  for(int i=1;i<=m;++i)
  {
    int u,v,r;cin>>u>>v>>r;
    add(u,v,r);arcadd(u,v,r);
  }
  spfa1(1);
  spfa2(1);
  cout<<res<<endl;
  return 0;
}

by ydkxj @ 2024-04-08 23:01:45

建边的问题?


by elpsconr @ 2024-04-12 01:29:54

@ydkxj 我用堆优化dijkstra过了,好像并不是建图的问题


|