寻旧 @ 2019-11-11 17:00:20
RT
谢谢!
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long LL;
LL read()
{
LL w=0;bool f=true;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=false;c=getchar();}
while(c>='0'&&c<='9')w=(w<<1)+(w<<3)+(c^48),c=getchar();
return f?w:~w+1;
}
const int N=1e6+50;
int n,m;LL Ans;
struct node
{
int id,dis;
friend bool operator <(node n1,node n2)
{
return n1.dis>n2.dis;
}
};
struct Graph
{
int to[N],val[N],nxt[N],fir[N],tot;
LL d[N];bool b[N];
void Add(int x,int y,int z)
{
to[++tot]=y;val[tot]=z;nxt[tot]=fir[x];fir[x]=tot;
}
void dijkstra(int S)
{
priority_queue<node>q;
memset(d,127/3,sizeof(d));
d[S]=0;q.push((node){S,d[S]});
while(!q.empty())
{
int x=q.top().id;q.pop();
if(b[x]) continue;
b[x]=true;
for(int k=fir[x];k;k=nxt[k]);
{
int y=to[k],z=val[k];
if(d[y]>d[x]+z)
{
d[y]=d[x]+z;
q.push((node){y,d[y]});
}
}
}
}
}G1,G2;
int main()
{
n=read();m=read();
for(int i=1;i<=m;++i)
{
int x=read(),y=read(),z=read();
G1.Add(x,y,z);G2.Add(y,x,z);
}
G1.dijkstra(1);G2.dijkstra(1);
for(int i=2;i<=n;++i) Ans+=G1.d[i]+G2.d[i];
printf("%lld\n",Ans);
return 0;
}
by gxy001 @ 2019-11-11 17:03:08
for(int k=fir[x];k;k=nxt[k]);
第45行分号去掉
by 寻旧 @ 2019-11-11 17:04:31
@gxy001
谢谢大佬
弱智错误