Uva 10917

题目链接：http://vjudge.net/contest/143062#problem/A

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

分析：

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

#include <bits/stdc++.h>
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<Edge> edges;
    vector<int> G[maxn];
    bool done[maxn];
    int d[maxn];
    int p[maxn];

    void init(int n)
    {
        this->n = n;
        for(int i=0; i<n; i++)
            G[i].clear();
        edges.clear();
    }

    void AddEdge(int from,int to,int dist)
    {
        edges.push_back((Edge)
        {
            from,to,dist
        });
        m = edges.size();
        G[from].push_back(m-1);
    }

    void dijkstra(int s)
    {
        priority_queue<HeapNode> Q;
        for(int i=0; i<n; i++)
            d[i] = INF;
        d[s] = 0;
        memset(done,0,sizeof(done));
        Q.push((HeapNode)
        {
            0,s
        });
        while(!Q.empty())
        {
            HeapNode x = Q.top();
            Q.pop();
            int u = x.u;
            if(done[u]) continue;
            for(int i=0; i<G[u].size(); i++)
            {
                Edge& e = edges[G[u][i]];
                if(d[e.to]>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<solve.G[u].size(); i++)
    {
        int v = solve.edges[solve.G[u][i]].to;
        if(solve.d[v]<solve.d[u]) ans +=dp(v);
    }
    return ans;
}

int main()
{

    int n,m;
    while(scanf("%d",&n),n)
    {
        scanf("%d",&m);
        solve.init(n);
        for(int i=0; i<m; i++)
        {
            int u,v,d;
            scanf("%d%d%d",&u,&v,&d);
            u--;
            v--;
            solve.AddEdge(u,v,d);
            solve.AddEdge(v,u,d);
        }

        solve.dijkstra(1);
        memset(d,-1,sizeof(d));
        printf("%d
",dp(0));
    }

    return 0;
}