文武武智障 @ 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 Dispwnl @ 2018-08-08 10:31:18
用高精（逃
by 花园Serena @ 2018-08-08 10:41:14
用无符号
by Resonaa @ 2018-08-08 11:01:11
@非正常智障 Python了解一下……
by 文武武智障 @ 2018-08-08 11:07:09
弃疗了
打完重载后样例都过不了
大佬帮忙看一下有什么错
#include<bits/stdc++.h>
using namespace std;
long long head1[1000010],head2[1000010];
long long n,m,num_edge1,num_edge2;
struct bignum
{
int len,s[100];
bignum(){memset(s,0,sizeof(s));len=1;}
bignum(int num){*this=num;}
bignum(const char *num){*this=num;}
bignum operator =(const char *num)
{
len=strlen(num);
for(int i=0;i<len;i++) s[i]=num[len-i-1]-'0';
return *this;
}
bignum operator =(const long long &num)
{
char a[1000010];
sprintf(a,"%d",num);
*this=a;
return *this;
}
bignum operator =(const int &num)
{
char a[1000010];
sprintf(a,"%d",num);
*this=a;
return *this;
}
bignum operator +(const bignum &a)
{
bignum c;
c.len=max(len,a.len)+1;
for(int i=0,x=0;i<c.len;++i)
{
c.s[i]=s[i]+a.s[i]+x;
x=c.s[i]/10;
c.s[i]=c.s[i%10];
}
if(c.s[c.len-1]==0) --c.len;
return c;
}
bool operator <(const bignum &x) const
{
if(len!=x.len) return len<x.len;
for(int i=len-1;i>=0;--i)
if(s[i]!=x.s[i]) return s[i]<x.s[i];
return false;
}
bool operator >(const bignum &x) const {return x<*this;}
}ans;
struct Edge
{
long long next;
long long to;
bignum dis;
}edge1[1000010],edge2[1000010];
inline long long read()
{
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;
}
bignum d[1000010];
bool v[1000010];
inline void SPFA1()
{
memset(d,0x3f3f3f3f,sizeof(d));
memset(v,0,sizeof(v));
queue<int> q;
d[1]=0;
q.push(1);
while(q.size())
{
int x=q.front();
q.pop();
v[x]=0;
for( int i=head1[x];i;i=edge1[i].next)
{
long long y=edge1[i].to;
if(d[y]>d[x]+edge1[i].dis)
{
d[y]=d[x]+edge1[i].dis;
if(!v[y]) { q.push(y); v[y]=1; }
}
}
}
for(int i=1;i<=n;i++)
ans=d[i]+ans;
}
inline void SPFA2()
{
memset(d,0x3f3f3f3f,sizeof(d));
memset(v,0,sizeof(v));
queue<int> q;
d[1]=0;
q.push(1);
while(q.size())
{
int x=q.front();
q.pop();
v[x]=0;
for( int i=head2[x];i;i=edge2[i].next)
{
long long y=edge2[i].to;
if(d[y]>d[x]+edge2[i].dis)
{
d[y]=d[x]+edge2[i].dis;
if(!v[y]) { q.push(y); v[y]=1; }
}
}
}
for( int i=1;i<=n;i++)
ans=ans+d[i];
}
int main(){
cin>>n>>m;
for( 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:10:56
@守望
by Dispwnl @ 2018-08-08 11:20:17
！
by Dispwnl @ 2018-08-08 11:20:49
@非正常智障 我就是开个玩笑啊QAQ
by Dispwnl @ 2018-08-08 11:21:01
这题不用高精啊。。。
by Dispwnl @ 2018-08-08 11:22:44
您代码中虽然开了long long但是最后输出还是用的%d...
by Dispwnl @ 2018-08-08 11:22:56
应该是这里错了。。。？