原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1142
分析：最短路+记忆化搜索。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<vector> 7 #include<queue> 8 #define ll long long 9 #define inf 0x6fffffff 10 #define maxn 1005 11 using namespace std; 12 struct edge 13 { 14 int to,time; 15 edge(int x,int y) 16 { 17 to=x;time=y; 18 } 19 }; 20 vector<edge>e[maxn]; 21 queue<int>q; 22 bool vis[maxn]; 23 int d[maxn],n,m,p[maxn]; 24 void spfa(const int s) 25 { 26 while(!q.empty())q.pop(); 27 for(int i=1;i<=n;i++) 28 { 29 d[i]=inf; 30 vis[i]=false; 31 } 32 d[s]=0;vis[s]=true; 33 q.push(s); 34 while(!q.empty()) 35 { 36 int u=q.front();q.pop(); 37 for(int i=0;i<e[u].size();i++) 38 { 39 if(d[e[u][i].to]>d[u]+e[u][i].time) 40 { 41 d[e[u][i].to]=d[u]+e[u][i].time; 42 if(!vis[e[u][i].to]) 43 { 44 vis[e[u][i].to]=true; 45 q.push(e[u][i].to); 46 } 47 } 48 } 49 vis[u]=false; 50 } 51 } 52 int dfs(int s)//记忆化搜索 53 { 54 if(p[s])return p[s]; 55 if(s==2)return 1; 56 int sum=0; 57 for(int i=0;i<e[s].size();i++) 58 { 59 if(d[s]>d[e[s][i].to]) 60 { 61 if(p[e[s][i].to])sum+=p[e[s][i].to]; 62 else sum+=dfs(e[s][i].to); 63 } 64 } 65 p[s]=sum; 66 return sum; 67 } 68 int main() 69 { 70 while(~scanf("%d",&n),n) 71 { 72 for(int i=0;i<maxn;i++)e[i].clear(); 73 scanf("%d",&m); 74 int u,v,t,ans=0; 75 for(int i=0;i<m;i++) 76 { 77 scanf("%d%d%d",&u,&v,&t); 78 e[u].push_back(edge(v,t)); 79 e[v].push_back(edge(u,t)); 80 } 81 spfa(2); 82 memset(p,0,sizeof(p)); 83 ans=dfs(1); 84 printf("%d ",ans); 85 } 86 return 0; 87 }