WA了好多次了,大概是一直没搞清题意。
题意:对边<a,b>,如果a到终点的距离小于b到终点的距离,那么b就可以到a,但是a就不能到b了,所以经过这样的一种筛选的方法之后,我们要在这样的图里寻找能从起点走到终点的路径的总数。
思路:先算出每一点到终点的最小距离;然后dfs记忆化搜索路径总数。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; #define MAXN 1100 #define INF 1000000000 int dis[MAXN]; bool vis[MAXN]; int maps[MAXN][MAXN]; int p[MAXN]; int n,m; void dijsktra(int start) { for(int i = 1; i <= n; i++) { dis[i] = INF; vis[i] = 0; } dis[start] = 0; for(int i = 1; i <= n; i++) { int min = INF,p; for(int j = 1; j <= n; j++) { if(!vis[j] && dis[j] < min) { min = dis[j]; p = j; } } vis[p] = 1; for(int j = 1; j <= n; j++) { if(!vis[j] && maps[p][j] && dis[p] + maps[p][j] < dis[j]) { dis[j] = dis[p] + maps[p][j]; } } } return ; } int dfs(int s){ if(p[s]!=-1)return p[s]; if(s == 2)return 1; int sum = 0; for(int i = 1; i <= n; i++){ if(maps[s][i] && dis[i] < dis[s]){ sum += dfs(i); } } p[s] = sum; return p[s]; } int main() { int s,t,v, i ; while(scanf("%d",&n),n) { scanf("%d",&m); memset(maps,0,sizeof(maps)); memset(p,-1,sizeof(p)); for(i = 0; i < m; i++) { scanf("%d%d%d",&s,&t,&v); maps[s][t] = maps[t][s] = v; } dijsktra(2); printf("%d\n",dfs(1)); } return 0; }