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过了,好像并不是建图的问题