uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1858

题目大意：

Jimmy下班后决定每天沿着一条不同的路径回家，欣赏不同的风景。他打算只沿着满足如下条件的（A,B）道路走：存在一条从B出发回家的路，比所有从A出发回家的路径都短。你的任务是计算一共有多少条不同的回家路径。其中公司的编号为1，家的编号为2.

思路：

题目给出的n于1000以内，所以我直接用了邻接矩阵了。

首先求出每个点回家的最短路径。dis[u]（SPFA或者dijkstra都可以）

题目说的存在一条从B出发回家的路，比所有从A出发回家的路径都短，即dis[B]<dis[A]，这样我们创建一个新的图，当dis[B]<dis[A]建立有向变A->B，然后用动态规划求解。

（没一个点要加上与他相连的所有边的次数）

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int INF=10000000;const int MAXN=1024;int dis[MAXN];int n,m;int map[MAXN][MAXN];int cango[MAXN][MAXN];int dp[MAXN];void SPFA(){	int start=2;	bool vis[MAXN]={0};	deque
        
          q;	q.push_back(start);	dis[start]=0;	vis[start]=true;	while(!q.empty())	{		int cur=q.front();		q.pop_front();		vis[cur]=false;		for(int i=1;i<=n;i++)			if(map[cur][i]+dis[cur] < dis[i])			{				dis[i]=map[cur][i]+dis[cur];				if(!vis[i])				{					vis[i]=true;					if(!q.empty() && dis[i] < dis[q.front()])						q.push_front(i);					else						q.push_back(i);				}			}	}}int dfs(int cur){	 if(dp[cur]!=-1)		 return dp[cur];  		 int temp=0;	for(int i=1;i<=n;i++)		if(cango[cur][i])		{			temp+=dfs( i );		}	return dp[cur]=temp;}int main(){	while(~scanf("%d",&n),n)	{		for(int i=1;i<=n;i++)		{			dis[i]=INF;			dp[i]=-1;			for(int j=1;j<=n;j++)			{								map[i][j]=INF;				cango[i][j]=0;			}		}		scanf("%d",&m);		for(int i=0;i
         
           dis[j] && map[i][j]!=INF) cango[i][j]=1; dp[2]=1; dfs(1); printf("%d\n",dp[1]); }}