首页 > 代码库 > hdu1142 A Walk Through the Forest
hdu1142 A Walk Through the Forest
题目大意:寻找一共有多少条符合题意的路。能够从点A走到点B的要求是:点A到终点的最短路 > 点B到终点的最短路。
思路:这时,我们就需要先求出所有点到终点的最短路,即可从终点出发,求出所有路的最短路。然后,我们再用记忆化搜索,求出所有点符合题意的点。
AC代码:
#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<queue> using namespace std; #define INF 0xfffffff vector<int>road[1005]; int map[1005][1005],d[1005],s[1005];//map记录从i到j的距离, //s为记录当前点符合题意的路的条数 int vis[1005]; int n,m; void spfa() { int i,u; memset(vis,0,sizeof(int)*(n+3)); for(i=1;i<=n;i++)d[i]=INF; d[2]=0; queue<int >q; q.push(2); vis[2]=1; while(!q.empty()) { u=q.front(); q.pop(); vis[u]=0; for(i=1;i<=n;i++) { if(d[i]>d[u]+map[u][i]) { d[i]=d[u]+map[u][i]; if(vis[i]==0) { q.push(i); vis[i]=1; } } } } } int dfs(int u) { int i; if(u==2)return 1; if(s[u])return s[u]; for(i=0;i<road[u].size();i++) { if(d[u]>d[road[u][i]]) { s[u]+=dfs(road[u][i]); } } return s[u]; } int main() { while(scanf("%d",&n)!=EOF) { int i,j; if(n==0)break; scanf("%d",&m); memset(s,0,sizeof(int)*(n+3)); for(i=0;i<=n;i++)road[i].clear(); for(i=0;i<=n;i++) for(j=0;j<=n;j++) { if(i==j)map[i][j]=0; else map[i][j]=INF; } while(m--) { int u,v,w; scanf("%d %d %d",&u,&v,&w); map[u][v]=map[v][u]=w; road[u].push_back(v); road[v].push_back(u); } spfa(); printf("%d\n",dfs(1)); } return 0; }
hdu1142 A Walk Through the Forest
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。