题目大意：对于图中节点要从起点走向终点，而且能从A节点走向B节点的条件是在B点存在一条到终点的路径，且这条路径的长度小于任何从A节点通往终点路径的长度，求共有几种走法。
对于图中限制条件，其实只要判断从B到终点的最短路径是否小于从A点到终点的最小距离，若小于，则可以，否则不可以。
经过这样转化后，题目将十分明显，深搜即可，但发现图中节点十分多，最多能达到1000个，所以深搜过程中要用记忆化搜索。
#include <stdio.h>
#include <string.h>
#define INF 2000000
int map[1010][1010],n,m;
int low[1010],s[1010];//low存放最短路径，s为标志数组，看某节点的最短路径是否求出
int cap[1010];//记忆化搜索用到的，cap[i]记录从节点i到终点的走法数目
int dfs(int i)//记忆化搜索
{
int j;
if(i==2)
return 1;
if(cap[i]!=0)
return cap[i];
for(j=1;j<=n;j++)
if(i!=j&&map[i][j]<INF&&low[j]<low[i])//限制条件
cap[i]+=dfs(j);
return cap[i];
}
int main()
{
int i,j,k;
int x,y,w;
int ans,min,u;
while(1)
{
memset(cap,0,sizeof(cap));
memset(s,0,sizeof(s));
scanf("%d",&n);
if(n==0)
break;
scanf("%d",&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j)
map[i][j]=0;
else
map[i][j]=INF;
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
map[y][x]=map[x][y]=w;
}
for(i=1;i<=n;i++)//用的是dijkstra算法
low[i]=map[2][i];
s[2]=1;
for(i=1;i<n;i++)
{
min=INF;
for(j=2;j<=n;j++)
{
if(s[j]==0&&low[j]<min)
{
min=low[j];
u=j;
}
}
s[u]=1;
for(j=1;j<=n;j++)
{
if(s[j]==0&&low[j]>low[u]+map[u][j]&&map[j][u]<INF)
low[j]=low[u]+map[u][j];
}
}
ans=dfs(1);
printf("%d
",ans);
}
return 0;
}