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<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
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<int> q;
q.push_back(start);
dis[start]=0;
vis[start]=true;
while(!q.empty())
{
int cur=q.front();
q.pop_front();
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.emptydis[i] < dis[q.front()])
q.push_front(i);
else
q.push_back(i);
}
}
vis[cur]=false;
}
}
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<m;i++)
{
int from,to,dis;
scanf("%d%d%d",&from,&to,&dis);
map[from][to]=map[to][from]=dis;
}
SPFA();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dis[i] > dis[j] && map[i][j]!=INF)
{
cango[i][j]=1;
}
dp[2]=1;
dfs(1);
printf("%d\n",dp[1]);
}
}