Knight_Master @ 2019-10-23 15:38:44
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll d[1000010],tot=0;
bool v[1000010];
ll first1[1000010],next1[1000010],ver1[1000010],edge1[1000010];
ll first2[1000010],next2[1000010],ver2[1000010],edge2[1000010];
void add(ll x,ll y,ll z){
next1[++tot]=first1[x];
first1[x]=tot;
ver1[tot]=y;
edge1[tot]=z;
next2[tot]=first2[y];
first2[y]=tot;
ver2[tot]=x;
edge2[tot]=z;
}
priority_queue <pair<ll,ll> >q;
void dijkstra1(ll p){
ll x,y,z;
memset(v,0,sizeof v);
for(ll i=1;i<=n;i++)
d[i]=0x7fffffff;
d[p]=0;
q.push(make_pair(0,p));
while(q.size()){
x=q.top().second,q.pop();
if(v[x]) continue;
v[x]=1;
for(ll i=first1[x];i;i=next1[i]){
y=ver1[i],z=edge1[i];
if(d[y]>d[x]+z){
d[y]=d[x]+z;
q.push(make_pair(-d[y],y));
}
}
}
}
void dijkstra2(ll p){
ll x,y,z;
memset(v,0,sizeof v);
for(ll i=1;i<=n;i++)
d[i]=0x7fffffff;
d[p]=0;
q.push(make_pair(0,p));
while(q.size()){
x=q.top().second,q.pop();
if(v[x]) continue;
v[x]=1;
for(ll i=first2[x];i;i=next2[i]){
y=ver2[i],z=edge2[i];
if(d[y]>d[x]+z){
d[y]=d[x]+z;
q.push(make_pair(-d[y],y));
}
}
}
}
inline ll read()
{
ll s=0,w=1;
char ch=getchar();
while(ch<='0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main(){
n=read();
m=read();
ll a,b,c;
for(ll i=1;i<=m;i++){
a=read();
b=read();
c=read();
add(a,b,c);
}
dijkstra1(1);
ll ans=0;
for(ll i=1;i<=n;i++)
ans+=d[i];
dijkstra2(1);
for(ll i=1;i<=n;i++)
ans+=d[i];****
printf("%lld",ans);
}
没有快读就TLE前三个
开了快读就RE前三个
by team0001 @ 2019-10-23 15:45:58
开o2
by Knight_Master @ 2019-10-23 15:49:48
@林度 大哥,我开了50个优化和洛谷自带O2,但还是re或是tle了
by Knight_Master @ 2019-10-23 15:59:13
是快读问题,sorry
by Knight_Master @ 2019-10-23 16:00:39
得用位运算