题意：假设a和b是相连的，当前在a处，如果a到终点的距离大于b到终点的距离，则可以从a通往b处，问满足这种的条件的路径条数。
开始看成了求最短路有多少条，wa了一发
题解：从2开始跑dijkstra，然后记忆化搜索
1 #include <bits/stdc++.h> 2 using namespace std; 3 int mm[1010][1010]; 4 int vis[1010],dis[1010]; 5 int p[1010]; 6 const int inf=0x3f3f3f3f; 7 int n,m; 8 int ans; 9 void dijtkstara(int s) 10 { 11 memset(vis,0,sizeof(vis)); 12 memset(dis,0x3f,sizeof(dis)); 13 dis[s]=0; 14 int mi,pos; 15 for(int i=1;i<=n;i++) 16 { 17 mi=inf; 18 for(int j=1;j<=n;j++) 19 { 20 if(dis[j]<mi&&!vis[j]) 21 { 22 mi=dis[j]; 23 pos=j; 24 } 25 } 26 vis[pos]=1; 27 for(int j=1;j<=n;j++) 28 { 29 if(dis[pos]+mm[pos][j]<dis[j]) 30 { 31 dis[j]=dis[pos]+mm[pos][j]; 32 } 33 } 34 } 35 } 36 37 int dfs(int s,int n) 38 { 39 if(p[s]) 40 return p[s]; 41 if(s==2) 42 return 1; 43 int sum=0; 44 for(int i=1;i<=n;i++) 45 { 46 if(mm[s][i]<inf&&dis[s]>dis[i]) 47 { 48 if(p[i]) 49 sum=sum+p[i]; 50 else 51 sum=sum+dfs(i,n); 52 } 53 } 54 sum=sum+p[s]; 55 p[s]=sum; 56 return p[s]; 57 } 58 int main() 59 { 60 while(~scanf("%d",&n)&&n) 61 { 62 scanf("%d",&m); 63 memset(mm,0x3f,sizeof(mm)); 64 while(m--) 65 { 66 int a,b,w; 67 scanf("%d%d%d",&a,&b,&w); 68 mm[a][b]=mm[b][a]=w; 69 } 70 dijtkstara(2); 71 memset(p,0,sizeof(p)); 72 printf("%d ",dfs(1,n)); 73 } 74 }