本文主要是介绍hdu 1142 dijkstra，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最短路径+ 记忆化搜索
注意转变思路，每一点到家的存在最短路径，则，以家为起点，寻找到每一点的最短路径。
dijkstra 单源最短路径 ，求的是 一个源s到其余每一点的最短路径
记忆化搜索
如果不对节点进行记忆化搜索，将会有大量重复搜索过程。如果记录结果，那么会减少搜索量。
要记录什么结果呢？
用一个数组记录每一个节点到终点有几条路径。如果遇到已经搜索过的节点，则直接返回就可以了，不必再重复搜索。
dijkstra 邻接表算法模板
oid dijkstra(){int start=over;queue<int> q;q.push(start);for(int i=1;i<=n;i++){d[i]=INF;visited[i]=false;}d[start]=0;visited[start]=true;int now;int next;int len;while(!q.empty()){now=q.front();q.pop();len=g[now].size();for(int i=0;i<len;i++){next=g[now][i];if(d[next]>d[now]+dist[now][next]){d[next]=d[now]+dist[now][next];if(!visited[next]){visited[next]=true;q.push(next);}}}visited[now]=false; //very import sometime maybe need back search}
}记忆化搜索代码：
//need remember search// the array p[i] mean from node i has how many routes
int dfs(int start){//if has visited start and get the num of routes from node start can get// then return ;if(p[start]) return p[start];//find over then find 1 route returnif(start==over){return 1;}int len=g[start].size();int next;int sum=0;for(int i=0;i<len;i++){next=g[start][i];// if(visited[next]) continue;if(d[start]>d[next]){// if has searchedif(p[next]) sum+=p[next];else{sum+=dfs(next);}}}p[start]=sum;return sum;
}
AC 代码
#include <iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>using namespace std;const int maxn=1005;
const int INF=((1<<31)-100)/2;
vector<int> g[maxn];
bool visited[maxn];
int dist[maxn][maxn];int d[maxn];int p[maxn];
int n;// number of intersectionsint m;// number of pathint ans=0; // the ansint over=2;
void dijkstra(){int start=over;queue<int> q;q.push(start);for(int i=1;i<=n;i++){d[i]=INF;visited[i]=false;}d[start]=0;visited[start]=true;int now;int next;int len;while(!q.empty()){now=q.front();q.pop();len=g[now].size();for(int i=0;i<len;i++){next=g[now][i];if(d[next]>d[now]+dist[now][next]){d[next]=d[now]+dist[now][next];if(!visited[next]){visited[next]=true;q.push(next);}}}visited[now]=false; //very import }}//need remember search// the array p[i] mean from node i has how many routes
int dfs(int start){//if has visited start and get the num of routes from node start can get// then return ;if(p[start]) return p[start];//find over then find 1 route returnif(start==over){return 1;}int len=g[start].size();int next;int sum=0;for(int i=0;i<len;i++){next=g[start][i];// if(visited[next]) continue;if(d[start]>d[next]){if(p[next]) sum+=p[next];else{sum+=dfs(next);}}}p[start]=sum;return sum;
}int main()
{while(scanf("%d",&n)){if(n==0) break;scanf("%d",&m);ans=0;//initfor(int i=1;i<=n;i++){g[i].clear();}//init dist;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)dist[i][j]=0;else{dist[i][j]=INF;dist[j][i]=INF;}}}//inputint a,b,d; // a --b is d distancefor(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&d);g[a].push_back(b);g[b].push_back(a);dist[a][b]=d;dist[b][a]=d;}//get the dijkstra distancedijkstra();// the array p[i] mean from node i has how many routesmemset(p,0,sizeof(p));ans=dfs(1);printf("%d\n",ans);}return 0;
}
这篇关于hdu 1142 dijkstra的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
