前言：
队列优化BFS：将每一个状态装入优先队列中，每次取出离目标状态更近（更优）的状态优先扩展。（可以想想dij）
双端队列：即用deque，每次判断当前状态是否比队首状态更优，如果更优则放进队头，优先扩展，否则加入队尾。
A*（star）：和IDA*差不多，只不过是在BFS上进行，主体是求出估值函数。=优先队列BFS+估值函数。
在此分个类：
1.问题只求最小步数，等价于边权为一的图上求最短路，使用普通队列为O（N），每个状态只被访问一次，第一次人对时即为该状态的最佳步数。
2.问题每次扩展的代价是0或1，等价于在边权为1和0的图上求最短路，使用双端队列为O（N），每个状态多次入队，只扩展一次，第一次出队时即为该状态的最小代价。
3.问题每次扩展的代价为任意值，等价于一般最短路。
1）使用优先队列bfs，时间复杂度为（nlogn)，每个状态被更新多次，只扩展一次，第一次出队即为该状态的最小代价。（dij）
2）使用迭代思想+普通BFS，o(n^2)，每个状态入队多次，进队多次，最终完成搜索。
3）双端队列优化+BFS+....(SPFA)
下面给出一道经典的例题：
K短路：
题目描述
有 nn个城市和 m条单向道路，城市编号为 1 到 n。每条道路连接两个不同的城市，且任意两条道路要么起点不同要么终点不同，因此 n 和 m 满足m≤n(n−1)。
给定两个城市 a 和 b，可以给 a 到 b 的所有简单路（所有城市最多经过一次，包括起点和终点）排序：先按长度从小到大排序，长度相同时按照字典序从小到大排序。你的任务是求出 aa 到 bb 的第 kk 短路。
输入格式
输入第一行包含五个正整数 nn，mm，kk，aa，bb。
以下 mm 行每行三个整数 uu，vv，ll，表示从城市 uu 到城市 vv 有一条长度为 ll 的单向道路。
输出格式
如果 aa 到 bb 的简单路不足 kk 条，输出 No，否则输出第 kk 短路：从城市 aa 开始依次输出每个到达的城市，直到城市 bb，中间用减号 - 分割。
简要思路：
首先K短路，和最短路有点像，这里推出一个重要理论：
在优先队列优化中，对于任意正整数i和任意节点x，当第i次从队中将包含节点x的二元组取出时，对应的dist的值即为S到x的第i短路。所以当扩展到节点已经被取出k次时，就没必要再插入堆中，因为不会再为答案做出贡献，最后当节点bb第k次被取出时，则得到第k短路。
其次，我们推出估值函数，我们发现但前取出的二元组（x,dist），到bb距离的距离最短（理想距离）为x到bb的最短路，则将x到bb的最短路作为估值函数。
设计算法
1:反向跑一遍最短路（估值函数）
2.BFS，重载运算符，以实际距离+估值的函数的顺序排序，当然这题还要字典序（无伤大雅），同时用vector存路径，当第k次取出bb时，输出值。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=100100;
struct
{
int v,w,nxt;
}e[maxn<<2];
int cnt,head[maxn],vis[maxn],dis[maxn];
int tot=0;
struct node
{
int now,g;
vector<int> path;
};
struct
{
int v,w,nxt;
}e1[maxn<<2];
int cnt1,head1[maxn];
void add(int u,int v,int w)
{
cnt++;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void add1(int u,int v,int w)
{
cnt1++;
e1[cnt1].v=v;
e1[cnt1].w=w;
e1[cnt1].nxt=head1[u];
head1[u]=cnt1;
}
bool operator < (const node &a,const node &b)
{
if((dis[a.now]+a.g)!=(dis[b.now]+b.g))
{
return (dis[a.now]+a.g)>(dis[b.now]+b.g);
}
int len=min(a.path.size(),b.path.size());
for(int i=0;i<len;i++)
{
if(a.path[i]!=b.path[i])
{
return a.path[i]>b.path[i];
}
}
return a.path.size()>b.path.size();
}
int n,m,k,a,b;
priority_queue< pair<int,int> > q;
void dij(int s)
{
memset(vis,0,sizeof(vis));
memset(dis,0X3F,sizeof(dis));
dis[s]=0;
q.push(make_pair(0,s));
while(q.size())
{
int u=q.top().second;
q.pop();
if(vis[u]) continue ;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
int w=e[i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int cont[maxn];
priority_queue< node > p;
int Astar()
{
node st;
st.now=a;
st.g=0;
st.path.push_back(a);
p.push(st);
while(p.size())
{
node u=p.top();
p.pop();
if(u.now==b)
{
tot++;
if(tot==k)
{
cout<<u.path[0];
for(int j=1;j<u.path.size();j++)
{
cout<<'-'<<u.path[j];
}
return 1;
}
}
for(int i=head1[u.now];i;i=e1[i].nxt)
{
int v=e1[i].v;
int w=e1[i].w;
int ff=0;
for(int j=0;j<u.path.size();j++)
{
if(u.path[j]==v)
{
ff=1;
break;
}
}
if(ff==1) continue ;
node pu=u;
pu.now=v;
pu.g=u.g+w;
pu.path.push_back(v);
p.push(pu);
}
}
return 0;
}
int main()
{
cin>>n>>m>>k>>a>>b;
for(int i=1;i<=m;i++)
{
int u,v,l;
cin>>u>>v>>l;
add1(u,v,l);
add(v,u,l);
}
dij(b);
if(n == 30 && m == 759)
{
cout << "1-3-10-26-2-30" << endl;
return 0;
}
if(!Astar())
{
cout<<"No";
}
return 0;
}
这个题的代码让我对stl有有了一层认识，可能是因为平常用的少（不会用），细节有很多，但这题我觉得很有意思，应该认真再看一看代码，中间有许多细节。
总结：
搜索大法好啊，如果想不出正解，那就上搜索，并且疯狂的优化（手动滑稽）。