?這道題的解題步驟是這樣的：
（1）用Dijkstra求出每個點到house（也就是2號點）的最短距離，我是記錄在數組dist[]中；
（2）我們要求的是office（1號點）到house（或2——>1)最短路徑的條數；
（3）記憶化搜索部分是基于這樣的事實，我們利用Dijkstra找到的從2號點到1號點的最短路徑中的每個點v，dist[v]都小于dist[1]。

http://acm.hdu.edu.cn/showproblem.php?pid=1142

/* 最短路徑模版(Dijkstra) 鄰接表+優先隊列 */ /* 1代表他的office，2代表他的house 題目要求的是1到2之間的最短路徑的數目。 首先就先求出2到所有點的最短路徑，然后再求2到1的最短路的數目。 下面是題目描述中的一句話 He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A. 這句話說明了，為什么要求2到所有點的最短距離，而不是求1到所有點的最短距離。 求 2到1 的最短路徑的數目時，需要用到DP的思想。 先找出2到1的最短路徑上，和1相鄰的頂點，然后再接著向前求，直到到2為止。 例如，從2到1的最短路徑上，經過點3，3和1相鄰。 那么可以保證3，4是符合上面那句描述中的點B的要求。 即 dist[3]<dist[1],接下來就變成求 2到3的最短路徑的數目， 2到1的最短路徑的數目，就是所有和1相鄰的，滿足上述要求的點的最短路徑數目之和。 */ #include<iostream> #include<queue> #include<cstdio> using namespace std; #include<memory.h>#define INF 0x3f3f3f3ftypedef struct {int v;int next;int cost; }Edge;typedef struct node {int v;int cost;friend bool operator<(node a, node b){ //從小到大排序采用“>”號；如果要從大到小排序，則采用“<”號return a.cost> b.cost; //從小到大排序} }node;const long MAXN=2009;int m,n; //邊,點 int head[MAXN],dp[MAXN],dist[MAXN]; Edge e[2000000]; bool visit[MAXN];inline void init() {int i,eid=0;int from,to,cost;memset(head,-1,sizeof(head));memset(visit,0,sizeof(visit));for(i=0;i<m;++i){scanf("%d %d %d",&from,&to,&cost);e[eid].next=head[from];e[eid].v=to;e[eid].cost=cost;head[from]=eid++;//以下為無向圖使用swap(from,to);e[eid].next=head[from];e[eid].v=to;e[eid].cost=cost;head[from]=eid++;} }int Dijkstra(int start,int end) //分別表示起點和終點 {int i,j;init();priority_queue<node> q;node cur;cur.cost=0;cur.v=start;q.push(cur);for(i=1;i<=n;++i)dist[i]=INF;dist[start]=0;while(!q.empty()){cur=q.top();q.pop();if (visit[cur.v])continue;visit[cur.v]=true;for (j=head[cur.v];j!=-1;j=e[j].next){if(dist[e[j].v] > cur.cost+e[j].cost){node temp;temp.v=e[j].v;dist[e[j].v] = cur.cost+e[j].cost;temp.cost = dist[temp.v];q.push(temp);}}}return dist[end]; } int dfs(int start) {if(dp[start]!=-1)return dp[start];if(start==2)return 1;int j,temp,sum=0;for(j=head[start];j!=-1;j=e[j].next){if(dist[start]>dist[e[j].v]){temp=dfs(e[j].v);sum+=temp;}dp[start]=sum; //dp[start]存儲的是從2到start的最短路徑數目 }return sum; } int main(void) {while(scanf("%d",&n)!=EOF){if(!n)break;scanf("%d",&m);Dijkstra(2,1);memset(dp,-1,sizeof(dp));dfs(1);printf("%d\n",dp[1]);}return 0; }

?

?

總結

以上是生活随笔為你收集整理的最短路径Dijkstra（静态邻接表+优先队列模板）+ 记忆化搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。