最短路径Dijkstra（静态邻接表+优先队列模板）+ 记忆化搜索

这道题的解题步骤是这样的：
（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 0x3f3f3f3f

typedef 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;
}