题意：
给你一个图，找最短路。但是有个非一般的的条件：如果a,b之间有路，且你选择要走这条路，那么必须保证a到终点的所有路都小于b到终点的一条路。问满足这样的路径条数 有多少，噶呜~~题意是搜了解题报告才明白的Orz.。。。英语渣~
思路：
1.1为起点，2为终点，因为要走ab路时，必须保证那个条件，所以从终点开始使用单源最短路Dijkstra算法，得到每个点到终点的最短路，保存在dis[]数组中。
2.然后从起点开始深搜每条路，看看满足题意的路径有多少条。
3.这样搜索之后，dp[1]就是从起点到终点所有满足题意的路径的条数。
AC_CODE:
#include<stdio.h>
#include<string.h>
#define INF 10000000
int map[][];
int vis[];
int dis[];
int n,m;
int dp[];
void dijkstra(int st)
{
int i,j,k;
memset(vis,,sizeof(vis));
for(i=;i<=n;i++)
{
if(i==st)
dis[i]=;
else
dis[i]=INF;
}
for(i=;i<=n;i++)
{
int r;
int min=INF;
for(j=;j<=n;j++)
{
if(!vis[j]&&dis[j]<min)
{
min=dis[j];
r=j;
}
}
vis[r]=;
for(k=;k<=n;k++)
{
if(dis[k]>dis[r]+map[r][k])
dis[k]=dis[r]+map[r][k];
}
}
return;
}
int DFS(int st)
{
int sum=;
if(dp[st]!=-)
return dp[st];
if(st==)
return ;
for(int i=;i<=n;i++)
{
if(map[st][i]!=INF&&dis[st]>dis[i])
sum+=DFS(i);
}
dp[st]=sum;
return dp[st];
}
int main()
{
int i,j,u,v,w;
while(scanf("%d",&n)!=EOF&&n)
{
for(i=;i<=n;i++)
{
dp[i]=-;
for(j=;j<=n;j++)
{
if(i==j)
map[i][j]=;
else
map[i][j]=INF;
}
}
scanf("%d",&m);
for(i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
map[u][v]=map[v][u]=w;
}
dijkstra();
printf("%d\n",DFS());
}
return ;
}
————Anonymous.PJQ