本文共 1238 字，大约阅读时间需要 4 分钟。
本来就是水题一道。
题意：一个人要从点1去到点2，中间还有很多点和很多条边。问你如果他每次走的边(a,b)都满足：a点到目标点的最短距离<b点到目标点的最短距离，那么他从点1出发到点2总共有多少条路径。
思路：先用Dijkstra求最短路，然后创一个图，对于满足条件的边(a,b)就加一条有向边，由于是严格按照小于加的边，图中绝对没有环，是个DAG。接下来dp就行了。
dp[i]表示i点出发有多少条路径，dp[i]=sum(dp[j])。
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxn=1005; 7 const int INF=0x3f3f3f3f; 8 struct Edge{ 9 int from,to,dist;10 };11 struct HeapNode{12 int d,u;13 bool operator < (const HeapNode& rhs) const14 {15 return d>rhs.d;16 }17 };18 struct Dijkstra{19 int n,m;20 int d[maxn],p[maxn];21 bool done[maxn];22 vector edges;23 vector G[maxn];24 void init(int n)25 {26 this->n=n;27 for(int i=0;i Q;39 int u;40 HeapNode x;41 for(int i=0;i d[e.from]+e.dist){53 d[e.to]=d[e.from]+e.dist;54 p[e.to]=G[u][i];55 Q.push((HeapNode){d[e.to],e.to});56 }57 }58 }59 }60 };61 int n;62 Dijkstra solver;63 vector Map[maxn];64 int dp[maxn];65 int dfs(int u)66 {67 if(dp[u]!=-1) return dp[u];68 if(u==1) return dp[u]=1;69 int ret=0;70 for(int i=0;i solver.d[v]) Map[u].push_back(v);92 }93 memset(dp,-1,sizeof(dp));94 printf("%d\n",dfs(0));95 }96 return 0;97 }
转载地址：http://nbhrb.baihongyu.com/