题意：看样子很多人都把这题目看错了，以为是求最短路的条数。真正的意思是：假设 A和B 是相连的，当前在 A 处，
如果 A 到终点的最短距离大于 B 到终点的最短距离，则可以从 A 通往 B 处，问满足这种的条件的从办公室到家的路径条数。
分析:1、以终点 2 为起点 Dijkstra跑一边最短路，找到所有点到2的最短距离；
2、直接DFS记忆化搜索。
注意:记忆化搜索时的return值，否则此很容易TLE
解法1:O(n^2)
#include<iostream> #include<cstdio> #include<cstring> #define inf 0x7fffffff int n,m,u,v,w; using namespace std; int g[1010][1010],dis[1010]; int vis[1010],path[1010]; void Dijkstra(int u) { memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) dis[i]=g[u][i]; dis[u]=0; vis[u]=1; for(int i=1;i<=n;i++){ int k,min=inf; for(int j=1;j<=n;j++){ if(!vis[j]&&min>dis[j]){ min=dis[j]; k=j; } } vis[k]=1; for(int j=1;j<=n;j++){ if(!vis[j]&&g[k][j]!=inf){//g[k][j]!=inf不能少 if(dis[j]>dis[k]+g[k][j]) dis[j]=dis[k]+g[k][j]; } } } } int dfs(int u) { if(path[u]!=-1) return path[u]; if(u==2) return 1;//记忆化搜索，如果该点已经访问过了，就返回从该点到终点的路径数 int num=0; for(int v=1;v<=n;v++){ if(g[u][v]!=inf&&dis[v]<dis[u]) num+=dfs(v); } path[u]=num;//不能直接return num,否则会TLE return path[u]; } int main() { while(scanf("%d",&n),n){ scanf("%d",&m); memset(path,-1,sizeof(path)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) g[i][j]=(i==j?0:inf); } for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); if(g[u][v]>w)//处理重边 g[u][v]=g[v][u]=w; } Dijkstra(2); cout<<dfs(1)<<endl; } return 0; }
解法2:刚开始dfs中TLE,修改后就一直WA...至今缘由不明，还是太菜了
#include<queue> #include<cstdio> #include<vector> #include<cstring> #define inf 0x7fffffff using namespace std; struct Node { int u,d; Node(long long uu,long long dd){ u=uu,d=dd; } friend bool operator < (Node a,Node b){ return a.d>b.d; } }; struct Edge { int v,w; Edge(long long vv,long long ww){ v=vv,w=ww; } }; bool vis[1010]; long long path[1010]; vector<Edge> g[1010];//为Edge类型 priority_queue<Node>que;//为Node类型 long long dis[1010]; void Dijkstra() { dis[2]=0; que.push(Node(2,0)); while(!que.empty()){ Node p=que.top(); que.pop(); long long u=p.u; if(!vis[u]){ vis[u]=1;//vis[u]=1位置不能放错 for(int i=0;i<g[u].size();i++){ long long v=g[u][i].v; long long c=g[u][i].w; if(!vis[v]){//这里不能写vis[v]=1; if(dis[v]>dis[u]+c){ dis[v]=dis[u]+c; que.push(Node(v,dis[v])); } } } } } } int dfs(int u) { if(path[u]!=-1) return path[u]; if(u==2) return 1;//找到终点，返回1条路 long long num=0;//注意num的位置 for(int i=0;i<g[u].size();i++){ int v=g[u][i].v; if(dis[v]<dis[u]) num+=dfs(v); } path[u]=num; return path[u];//返回从u到终点的所有路径数 } int main() { long long n,m,u,v,w; while(scanf("%lld",&n),n){ scanf("%lld",&m); memset(g,0,sizeof(g));//切记清零 memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) dis[i]=inf; for(int i=1;i<=m;i++){ scanf("%lld%lld%lld",&u,&v,&w); g[u].push_back(Edge(v,w)); g[v].push_back(Edge(u,w)); } Dijkstra(); memset(path,-1,sizeof(path));//初始化 printf("%lld ",dfs(1)); } }