Dijkstra
这个因为数据量相比前一题要大所以要优化,最开始以为我上一题的代码就足够AC了但没想到TLE了。
下面是AC和TLE代码不知道看帖子的带佬能不能看出差别。
TLE
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int sz=1e5+1;
int n,m,v[sz],h[sz],e[sz],nt[sz],ct,d[sz],f[sz];
void add(int x,int y,int z){v[++ct]=y,nt[ct]=h[x],e[ct]=z,h[x]=ct;}
int dj(int zx,int zy)
{
int i,x,y;for(i=1;i<=n;++i)d[i]=1e9;d[zx]=0;
priority_queue<pair<int,int> >q;q.push({0,zx});
while(q.size())
{
x=q.top().second;q.pop();
for(i=h[x];y=v[i],i;i=nt[i])
if(d[y]>d[x]+e[i])
{
d[y]=d[x]+e[i];q.push({-d[y],y});
}
}
return d[zy];
}
int main()
{
int i,x,y,z,s;
scanf("%d%d",&n,&m);
for(i=0;i<m;++i)scanf("%d%d%d",&x,&y,&z),add(x,y,z);
s=dj(1,n);
printf("%d",s==1e9?-1:s);
return 0;
}
AC代码
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int sz=1e5+1+5e4;
int n,m,v[sz],h[sz],e[sz],nt[sz],ct,d[sz],f[sz];
void add(int x,int y,int z){v[++ct]=y,nt[ct]=h[x],e[ct]=z,h[x]=ct;}
int dj(int zx,int zy)
{
int i,x,y;for(i=1;i<=n;++i)d[i]=1e9;d[zx]=0;
priority_queue<pair<int,int> >q;q.push({0,zx});
while(q.size())
{
x=q.top().second;q.pop();
if(!f[x])
for(f[x]=1,i=h[x];y=v[i],i;i=nt[i])
if(d[y]>d[x]+e[i])
{
d[y]=d[x]+e[i];q.push({-d[y],y});
}
}
return d[zy];
}
int main()
{
int i,x,y,z,s;
scanf("%d%d",&n,&m);
for(i=0;i<m;++i)scanf("%d%d%d",&x,&y,&z),add(x,y,z);
s=dj(1,n);
printf("%d",s==1e9?-1:s);
return 0;
}
差别就在这个F数组,因为已经更新过的就没必要更新。
打个比方就是你一直保持着最优的选项第一点是最近的第二点是最近的所以它们更新的点也是最近的。
那为什么要这个F数组呢?
因为即使没有也能做出来但是这样会多做很多事情,就算你不更新它但你还是多遍历了一遍又一遍。
心得
所以做题还是得细心。
想到之前还发了个帖子就是用了优先队列,但里面并没有F数组。
现在加上了也算是进步了?
还是得细心不然以后考场上因为这点事WA或者TLE了那真是一时失足千古恨。。。