UVA10917_Walk Through the Forest

无向图。对于两个相连的点，如果A到终点的最短路径大于B到终点的最短路径，那么A可以往B走，求最终从起点到终点有多少种走法？

首先我们可以直接预处理所有点到终点的最短路径。然后分别判断所有的边两点是否满足d[U[i]]>d[V[i]]，然后把把满足条件的加入到一个新图中即可。

由于新图是一个有向无环图，那么只需要记忆话搜就可以解决问题了。

召唤代码君：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#define maxn 1010

#define maxm 2222222

using namespace std;

struct heapnode{

    int D,U;

    bool operator < (heapnode HP) const{

        return D>HP.D;

    }

};

const int inf=~0U>>;

int to[maxm],next[maxm],c[maxm],first[maxn],edge;

int d[maxn],f[maxn];

bool done[maxn];

int n,m;

int U[maxm],V[maxm],W[maxm];

void _init()

{

    edge=-;

    for (int i=; i<=n; i++) first[i]=f[i]=-,d[i]=inf,done[i]=false;

}

void addedge(int uu,int vv,int ww)

{

    edge++;

    to[edge]=vv,c[edge]=ww,next[edge]=first[uu],first[uu]=edge;

}

void dijkstra(int t)

{

    priority_queue<heapnode> Q;

    Q.push((heapnode){,t}),d[t]=;

    while (!Q.empty())

    {

        heapnode cur=Q.top();

        Q.pop();

        int V=cur.U;

        if (done[V]) continue;

        done[V]=true;

        for (int i=first[V]; i!=-; i=next[i])

            if (d[V]+c[i]<d[to[i]])

                d[to[i]]=d[V]+c[i],Q.push((heapnode){d[to[i]],to[i]});

    }

}

int get(int x)

{

    if (f[x]!=-) return f[x];

    if (x==) return f[x]=;

    f[x]=;

    for (int i=first[x]; i!=-; i=next[i])

        f[x]+=get(to[i]);

    return f[x];

}

int main()

{

    while (scanf("%d",&n) && n)

    {

        scanf("%d",&m);

        _init();

        for (int i=; i<=m; i++)

        {

            scanf("%d%d%d",&U[i],&V[i],&W[i]);

            addedge(U[i],V[i],W[i]);

            addedge(V[i],U[i],W[i]);

        }

        dijkstra();

        edge=-;

        for (int i=; i<=n; i++) first[i]=-;

        for (int i=; i<=m; i++)

        {

            if (d[U[i]]>d[V[i]]) addedge(U[i],V[i],);

                else if (d[V[i]]>d[U[i]]) addedge(V[i],U[i],);

        }

        printf("%d\n",get());

    }

    return ;

}