总结搜索和最短路径问题

DFS
BFS
Dijkstra
Spfa
Floyd

① DFS：

无权图的最短路（1131 Subway Map）
遍历
合并剪枝使用 1103 Integer Factorization

 1 #include <iostream>
 2 #include <unordered_map>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <cmath>
 6 using namespace std;
 7 const int maxn = 410;
 8 
 9 int n,k,p;
10 int list[maxn];
11 vector<int> path,tmppath;
12 int maxSum=0;
13 int cnt=0;
14 int ptr=0;
15 
16 bool cmp(int a,int b){
17     return a>b;
18 }
19 
20 void dfs(int v,int value,int sum,int len){
21     tmppath.push_back(v);
22     if(len==k){
23         if(len==k&&value==n&&sum>=maxSum){
24             path=tmppath;
25             maxSum=sum;
26         }
27         tmppath.pop_back();
28         return;
29     }
30     for(int i=v;i<=ptr;i++){
31         if(value+list[i]<=n)
32             dfs(i,value+list[i],sum+i,len+1);
33     }
34     tmppath.pop_back();
35     return;
36 }
37 
38 int main(){
39     scanf("%d%d%d",&n,&k,&p);
40     
41     for(int i=0;i<maxn;i++,ptr++){
42         list[i]=pow(i, p);
43         if(list[i]>=n) break;
44     }
45     /*printf("%d
",ptr);
46     for(int i=0;i<maxn;i++){
47         printf("%d ",list[i]);
48     }*/
49     for(int i=1;i<=ptr;i++){
50         //printf("%d ",i);
51         dfs(i,list[i],i,1);
52     }
53     if(path.size()==0){
54         printf("Impossible");
55         return 0;
56     }
57     printf("%d = ",n);
58     sort(path.begin(), path.end(),cmp);
59     for(int i=0;i<path.size();i++){
60         if(i!=0) printf(" + ");
61         printf("%d^%d",path[i],p);
62     }
63 }

View Code

② BFS

无权图的最短路（Saving James Bond - Hard Version）
层序遍历

③ Dijkstra

有权图的最短路
不能处理负边
可以搭配dfs处理复杂的条件（1018Public Bike Management）

④ Spfa 万能

有权图最短路
可以处理负边
可以判别负环

 1 void  spfa(s);  //求单源点s到其它各顶点的最短距离
 2     for i=1 to n do { dis[i]=∞; vis[i]=false; }   //初始化每点到s的距离，不在队列
 3     dis[s]=0;  //将dis[源点]设为0
 4     vis[s]=true; //源点s入队列
 5     head=0; tail=1; q[tail]=s; //源点s入队, 头尾指针赋初值
 6     while head<tail do {
 7        head+1;  //队首出队
 8        v=q[head];  //队首结点v
 9        vis[v]=false;  //释放对v的标记，可以重新入队
10        for 每条边(v,i)  //对于与队首v相连的每一条边
11         if (dis[i]>dis[v]+a[v][i])  //如果不满足三角形性质
12          dis[i] = dis[v] + a[v][i]   //松弛dis[i]
13         if (vis[i]=false) {tail+1; q[tail]=i; vis[i]=true;} //不在队列，则加入队列
14     } 
15 
16 //https://blog.csdn.net/xunalove/article/details/70045815

⑤ Floyd

多源最短路

总结 搜索和最短路径问题

总结搜索和最短路径问题