题目链接：

题意：一个人要从点1去到点2，中间还有很多点和很多条边。问你如果他每次走的边(a,b)都满足：a点到目标点的最短距离<b点到目标点的最短距离，那么他从点1出发到点2总共有多少条路径。

分析：

从家出发使用dijkstra,题目的条件"存在一条从B出发回家的路径，比所有从A出发的路径都短"，实际上就是 d[B] < d[A],这样，就有：一条有向边 A->B，建立新图。从起点出发到终点有多少条路。DAG模型。

 

#include 
     
      using namespace std;const int maxn = 1000+ 10;const int INF = 0x3f3f3f3f;struct Edge{    int from,to,dist;};struct HeapNode{    int d,u;    bool operator < (const HeapNode& rhs) const    {        return d > rhs.d;    }};struct Dijkstra{    int n,m;    vector
      
        edges;    vector
       
         G[maxn];    bool done[maxn];    int d[maxn];    int p[maxn];    void init(int n)    {        this->n = n;        for(int i=0; i
        
          Q;        for(int i=0; i
         
          d[u]+e.dist)                {                    d[e.to] = d[u] + e.dist;                    p[e.to] = G[u][i];                    Q.push((HeapNode)                    {                        d[e.to],e.to                    });                }            }        }    }};Dijkstra solve;int d[maxn];int dp(int u){    if(u==1) return 1;    int& ans = d[u];    if(ans>=0) return ans;    ans = 0;    for(int i=0; i