一下午都在学最短路dijkstra算法，总算是优化到了我能达到的水平的最快水准，然后列举一下我的优化历史，顺便总结总结
最朴素算法:
邻接矩阵存边+贪心||dp思想，几乎纯暴力，luoguTLE+MLE，
算优点？？：但好写好想，比下面的代码短了差不多一半。
#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std; int main()
{
int a[][],point,i,j,k,number,t1,t2,t3,u,n,min,book[]={},dis[];
int inf=;
scanf("%d %d\n",&point,&number);
int x;
cin>>x;
for(int i=;i<=point;i++)
for(int j=;j<=point;j++)
if(i==j)a[i][j]=;
else
a[i][j]=inf; for(int i=;i<=number;i++)
{
cin>>t1>>t2>>t3;
a[t1][t2]=t3;
} for(int i=;i<=point;i++)
dis[i]=a[][i]; for(int i=;i<=point-;i++)
{
min=inf;
for(int j=;j<=point;j++)
if(book[j]==&& dis[j]<min)
{
min=dis[j];
u=j;
}
book[u]=;
for(int k=;k<=point;k++)
{
if(a[u][k]<inf)
if(dis[k]>dis[u]+a[u][k])
dis[k]=dis[u]+a[u][k];
}
}
for(int i=;i<=point;i++)
cout<<i<<" "<<dis[i]<<endl;
return ;
}
第一次优化是前向星存边，
比上面最朴素的大量省空间，也省了部分时间，luogu上共用时1400ms+，一个点max接近五百。
#include<iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
# include <cstdio>
#define maxi 2147483647; using namespace std; struct node
{
int z;//子节点
int val;//权值
int nexty;//最近父节点相同边编号
}edge[];
int head[];//某点为父节点运出的最后一条边
int cnt=,curr;// 边id inline void add(int a,int b,int c)//建立边向前星
{
cnt++;
edge[cnt].z=b;
edge[cnt].val =c;
edge[cnt].nexty =head[a];
head[a]=cnt;
} int main()
{
bool visit[]={};//是否已经加入最短路
long long dis[];//最短路存值
int n,m,s;
int a,b,c; scanf("%d%d%d",&n,&m,&s);
for(int i=;i<=n;i++)//初始化边权值为无穷
dis[i]=maxi;
for(int i=;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
//读入
curr=s;
dis[s]=;//到最初点距离为零
long long minn; while(!visit[curr])
{
visit[curr]=true;
for(int i=head[curr];i!=;i=edge[i].nexty )
{
if(!visit[edge[i].z]&&dis[edge[i].z]>dis[curr]+edge[i].val )
dis[edge[i].z]=dis[curr]+edge[i].val;
}
minn=;
for (int i=;i<=n;i++)
if(!visit[i]&&minn>dis[i])
{
minn=dis[i];
curr=i;
}
}
for (int i=;i<=n;i++)
printf("%lld ",dis[i]);
return ;
}
dijkstra优化1
最后的优化使代码长达近百行
主要运用：快读快写，优先队列（堆），前向星存边
不过这次优化使用结构体存边的时候发生了玄学错误，现在还是找不出错，不过用几个数组存边就AC了？？？
个人是喜欢结构体的，毕竟好写也整齐，但是没通过的话就不发出来了
这个复杂度又比上一个程序降低了不少，luogu 共用时500+ms，单个点max160+ms，比上一个快了大概3,4倍
下面这个是ac的数组存边。
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <string.h>
#define maxn 10005
#define maxm 500005
#define inf 2147483647 using namespace std; int n,m,cnt=;
bool visit[maxn];
int head[maxm],next[maxm],v[maxm],w[maxm],dist[maxn]; inline int read()
{
char ch;
int a=;
while(!(((ch=getchar())>='')&&(ch<='')));
a*=;a+=ch-'';
while(((ch=getchar())>='')&&(ch<=''))a*=,a+=ch-'';
return a;
} void write(int x)
{
if(x<) putchar('-'),x=-x;
if(x>)write(x/);
putchar(x%+'');
return ;
} struct cmp
{
bool operator()(int x,int y)
{
return dist[x]>dist[y];
}
}; void add(int a,int b,int c)
{
v[cnt]=b;
w[cnt]=c;
next[cnt]=head[a];
head[a]=cnt++;
return ;
} void dijk(int s)
{
priority_queue<int,vector<int>,cmp> q2;
while(!q2.empty() )
q2.pop() ;
dist[s]=;
q2.push(s);
while(!q2.empty() )
{
int x=q2.top() ;
q2.pop() ;
if(!visit[x])
{
visit[x]=true;
for(int i=head[x];i!=-;i=next[i])
{
int y=v[i];
dist[y]=min(dist[y],dist[x]+w[i]);
q2.push(y);
}
}
}
return ;
} int main()
{
int s;
n=read();
m=read();
s=read();
memset(head,-,sizeof(head));
memset(visit,,sizeof(visit));
for(int i=;i<=m;i++)
{
int a,b,c;
a=read(),b=read(),c=read();
add(a,b,c);
}
for(int i=;i<=n;i++)
dist[i]=inf;
dijk(s);
for(int i=;i<=n;i++)
write(dist[i]),putchar(' ');
return ;
}
dijkstra优化2
注意！这不是最优化dijkstra，只是个人能力能达到的最优化了。。。
写那么长的代码还是挺有成就感的