XZYQvQ @ 2017-05-06 22:28:51
真没时间调了。。。只能明天再来看了。。。
要是有dalao能帮我看下这个代码为啥会tle就好了。。。
（也可能是我sb没看清题。。。）
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<typename _Tp>void in(_Tp & dig)
{
char c=getchar();dig=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct node{LL d1,d2;node*nxt;node(){d1=d2=0,nxt=NULL;}};
struct lst
{
node*begin,*end;
lst(){begin=end=NULL;}
void push_back(LL d1,LL d2)
{
node*p=new node;p->d1=d1,p->d2=d2;
if(begin==NULL)begin=end=p;else end=end->nxt=p;
}
}l[1000005],ul[1000005];
LL n,m,dis1[1000005],dis2[1000005],ans,que[5000005],qh,qt;
bool inque[1000005];
void push(LL d){que[qt++]=d;}
void pop(){qh++;}
int main()
{
in(n),in(m);
for(LL i=1,u,v,w;i<=m;i++)
in(u),in(v),in(w),l[u].push_back(v,w),ul[v].push_back(u,w);
for(LL i=2;i<=n;i++)dis1[i]=dis2[i]=10000000000000000ll;
push(1),inque[1]=1;
while(qh!=qt)
{
LL f=que[qh];pop(),inque[f]=0;
for(node*i=l[f].begin;i!=NULL;i=i->nxt)
if(dis1[f]+i->d2<dis1[i->d1])
{
dis1[i->d1]=dis1[f]+i->d2;
if(!inque[i->d1])push(i->d1),inque[i->d1]=1;
}
}
qh=qt=0,push(1),inque[1]=1;
while(qh!=qt)
{
LL f=que[qh];pop(),inque[f]=0;
for(node*i=ul[f].begin;i!=NULL;i=i->nxt)
if(dis2[f]+i->d2<dis2[i->d1])
{
dis2[i->d1]=dis2[f]+i->d2;
if(!inque[i->d1])push(i->d1),inque[i->d1]=1;
}
}
for(LL i=2;i<=n;i++)ans+=dis1[i]+dis2[i];
printf("%lld\n",ans);
return 0;
}by XZYQvQ @ 2017-05-07 00:20:32
我靠这题卡常数啊！
手打链表不停地new空间就tle了！
只能用数组模拟链表！
AC代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<typename _Tp>inline void in(_Tp & dig)
{
char c=getchar();dig=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct graph
{
int to[1000005],dis[1000005],nxt[1000005],head[1000005],cnt;
inline graph(){memset(head,-1,sizeof(head)),cnt=0;}
inline void adde(int u,int v,int w)
{
cnt++,to[cnt]=v,dis[cnt]=w,nxt[cnt]=head[u],head[u]=cnt;
}
};
int n,m,que[5000005],qh,qt;
LL dis[1000005],ans;
graph l,ul;
bool inque[1000005];
inline void push(LL d){que[qt++]=d;}inline void pop(){qh++;}
int main()
{
in(n),in(m);
for(int i=1,u,v,w;i<=m;i++)
in(u),in(v),in(w),l.adde(u,v,w),ul.adde(v,u,w);
for(int i=2;i<=n;i++)dis[i]=(LL)1e16;
push(1),inque[1]=1;
while(qh<qt)
{
int f=que[qh];pop(),inque[f]=0;
for(int i=l.head[f];i!=-1;i=l.nxt[i])
if(dis[l.to[i]]>dis[f]+l.dis[i])
{
dis[l.to[i]]=dis[f]+l.dis[i];
if(!inque[l.to[i]])push(l.to[i]),inque[l.to[i]]=1;
}
}
qh=qt=0,push(1),inque[1]=1;
for(int i=2;i<=n;i++)ans+=dis[i],dis[i]=(LL)1e16;
while(qh<qt)
{
int f=que[qh];pop(),inque[f]=0;
for(int i=ul.head[f];i!=-1;i=ul.nxt[i])
if(dis[ul.to[i]]>dis[f]+ul.dis[i])
{
dis[ul.to[i]]=dis[f]+ul.dis[i];
if(!inque[ul.to[i]])push(ul.to[i]),inque[ul.to[i]]=1;
}
}
for(int i=2;i<=n;i++)ans+=dis[i];
printf("%lld\n",ans);
return 0;
}by litble @ 2017-05-09 21:36:33
然而我从来都是手打链表，因为蒟蒻不会打真链表.....
所以这题的卡常对我无效啊.....