飘啊飘 @ 2020-05-21 11:52:22
#include<bits/stdc++.h>
using namespace std;
long long m,n,a,b,c,tot;
const long long u=1000005;
long long head[u],ver[u],net[u],edge[u],st[u],dist[u],head2[u],dist2[u],ans;
typedef pair <long long,long long> PII;
priority_queue <PII,vector<PII>,greater<PII> > q;
int read()
{
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
void write(long long x)
{
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
void add(long long a,long long b,long long c)
{
net[++tot]=head[a];
head[a]=tot;
ver[tot]=b;
edge[tot]=c;
}
void add2(long long a,long long b,long long c)
{
net[++tot]=head2[a];
head2[a]=tot;
ver[tot]=b;
edge[tot]=c;
}
void dijstla()
{
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
q.push({0,1});
while(!q.empty())
{
PII temp=q.top();
q.pop();
long long dis=temp.first,v1=temp.second;
if(st[v1]==1)
continue;
st[v1]=1;
for(long long i=head[v1];i;i=net[i])
{
long long v=ver[i];
if(dist[v]>dis+edge[i])
{
dist[v]=dis+edge[i];
q.push({dist[v],v});
}
}
}
for(long long i=1;i<=n;++i)
ans+=dist[i];
}
void dijstla2()
{
memset(dist2,0x3f,sizeof(dist2));
dist2[1]=0;
q.push({0,1});
while(!q.empty())
{
PII temp=q.top();
q.pop();
long long dis=temp.first,v1=temp.second;
if(st[v1]==1)
continue;
st[v1]=1;
for(long long i=head2[v1];i;i=net[i])
{
long long v=ver[i];
if(dist2[v]>dis+edge[i])
{
dist2[v]=dis+edge[i];
q.push({dist2[v],v});
}
}
}
for(long long i=1;i<=n;++i)
ans+=dist2[i];
}
int main()
{
n=read();
m=read();
for(long long i=1;i<=m;++i)
{
a=read();
b=read();
c=read();
add(a,b,c);
add2(b,a,c);
}
dijstla();
memset(st,0,sizeof(st));
dijstla2();
write(ans);
return 0;
}
by FZzzz @ 2020-05-21 11:54:48
因为你用的是 dijstla
by hjx__hjx @ 2020-05-21 11:55:18
您好像已经A了
by the_hidden_corner @ 2020-05-21 11:55:50
@飘啊飘 没看代码,但是用了快读还TLE一般就是代码/思路问题了......但是也不排除这几天泥古评测机比较咕..
by FZzzz @ 2020-05-21 11:56:24
我寻思你这不是 A 了吗/yiw
by XeCtera @ 2020-05-21 11:58:16
您这算滥用ll吧(
by 飘啊飘 @ 2020-05-21 11:58:51
@hjx__hjx 用的是同学的代码,感觉同学的代码跟我差不多,但我的不知为啥超时
by the_hidden_corner @ 2020-05-21 11:59:14
@HoneyLemon 您眼好快/kk看错还以为读入就要ll
by the_hidden_corner @ 2020-05-21 12:00:35
@飘啊飘 多交几次......洛谷比较卡常,或者您可以写超快读
by 飘啊飘 @ 2020-05-21 12:02:17
@明日世界 其实我快读都是百度的
by XeCtera @ 2020-05-21 12:04:19
滥用ll会增大一些常数 建议改掉