本文主要是介绍1142A Walk Through the Forest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
公司和家之间隔着一片森林，回家的路有多条，但是每两个岔路口之间只有一条直通的路，如果从公司出发，走a->b这条路的前提是a到家的距离要比b到家的距离远。现在问你最多有多少种走法！
解题思路：
没认真分析完题目就开始写代码的都是瞎搞，分析完题目后不认真写代码的都是扯淡，出现bug后只会找关键点错误的更是傻逼,为了赋值的时候多写了个==找了大半天，oh!no!.
本题其实就是先利用dijkstra,spfa,bellman中的任意一种先计算出各个点到家的最短路，然后dfs出所有满足条件的可能即可！
#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#define N 1005
#define inf 0x3fffffff
using namespace std;
struct node{int v;int dis;
};
int dis[N],dp[N];
vector<node>G[N];
bool in_s[N];
struct cmp
{bool operator()(int a,int b){return dis[a]>dis[b];}
};
void spfa(int st,int n){int ui,vi,i,cur,di;for(i=0;i<=n;i++){dis[i]=inf;in_s[i]=false;}priority_queue<int,vector<int>,cmp> s;s.push(st);in_s[st]=true;dis[st]=0;while(!s.empty()){cur=s.top();s.pop();in_s[cur]=false;//这个等号找了半天，啥也不说了！for(i=0;i<G[cur].size();i++){vi=G[cur][i].v;di=G[cur][i].dis;if(dis[vi]>dis[cur]+di){dis[vi]=dis[cur]+di;if(!in_s[vi]){in_s[vi]=true;s.push(vi);}}}}
}
int dfs(int vi){if(vi==2)return 1;if(dp[vi]>0)return dp[vi];for(int i=0;i<G[vi].size();i++){int to=G[vi][i].v;if(dis[vi]>dis[to]){dp[vi]+=dfs(to);}}return dp[vi];
}
int main()
{int n,m,a,b,d,i,j;node temp;while(scanf("%d",&n)&&n){scanf("%d",&m);for(i=0;i<=n;i++)G[i].clear();for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&d);temp.dis=d;temp.v=a;G[b].push_back(temp);temp.v=b;G[a].push_back(temp);}spfa(2,n);memset(dp,0,sizeof(dp));printf("%d\n",dfs(1));}}
这篇关于1142A Walk Through the Forest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
