UVa10917

题目链接

分析：
我现在深刻怀疑歪果人的表达能力
看看这个题面：
He considerstaking a path from A to B to beprogress if there exists a route from B to his home that is shorter than any possible route from A.
他只沿着满足如下条件的道路（A,B）走：
存在一条从B出发回家的路径，比所有从A出发回家的路径都短

实际上是指从家出发做dijkstra，当且仅当dis[B] < dis[A]加入A—>B的有向边

注意

A—>B的有向边必须是原图中就存在的一条边

我们求出dis数组之后，重新建一个图
新建出来的图是一个DAG
我们就可以用dp解决路径计数的问题了

tip

循环所有的边（共m条）进行判断加边就好了
挺方便的

//这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long

using namespace std;

const int INF=0x3f3f3f3f;
const int N=1005;
const int S=1;
const int E=2;
int n,m,dist[N];
int f[N];
vector<int> G2[1010]; 

struct node{
    int x,y,v;
};

struct heapnode{
    int d,u;
    bool operator < (const heapnode &a) const
    {
        return d>a.d;
    }
};

struct Dijkstra{
    int n,m;
    vector<node> e;
    vector<int> G[N];
    int dis[N];
    int pre[N];
    bool p[N];

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

    void add(int u,int w,int z)
    {
        e.push_back((node){u,w,z});
        m=e.size();
        G[u].push_back(m-1);
    }

    void dij(int s)
    {
        for (int i=1;i<=n;i++) dis[i]=INF;
        memset(pre,0,sizeof(pre));
        memset(p,1,sizeof(p));
        dis[s]=0;

        priority_queue<heapnode> Q;
        Q.push((heapnode){0,s});

        while (!Q.empty())
        {
            heapnode now=Q.top(); Q.pop();
            int u=now.u;
            if (!p[u]) continue;

            p[u]=0;

            for (int i=0;i<G[u].size();i++)
            {
                node way=e[G[u][i]];
                if (dis[way.y]>dis[u]+way.v)
                {
                    dis[way.y]=dis[u]+way.v;
                    pre[way.y]=G[u][i];
                    Q.push((heapnode){dis[way.y],way.y});
                }
            }
        }
    }
};
Dijkstra A;

int solve(int now)
{
    if (f[now]!=-1) return f[now];
    if (now==E)
    {
        f[now]=1;
        return f[now];
    }   
    int ans=0;
    for (int i=0;i<G2[now].size();i++)
    {
        int v=G2[now][i];
        ans+=solve(v);
    }
    f[now]=ans;
    return f[now];
}

int main()
{
    int cnt=0;
    scanf("%d",&n);
    while (n)
    {
        scanf("%d",&m);

        A.init(n);

        for (int i=1;i<=m;i++)
        {
            int u,w,z;
            scanf("%d%d%d",&u,&w,&z);
            A.add(u,w,z);
            A.add(w,u,z);
        }

        A.dij(E);
        for (int i=1;i<=n;i++) dist[i]=A.dis[i];
        for (int i=1;i<=n;i++) G2[i].clear();
        for (int i=0;i<A.m;i++)
        {
            node way=A.e[i];
            int u=way.x,v=way.y;
            if (A.dis[u]>A.dis[v])
                G2[u].push_back(v);
        }

        memset(f,-1,sizeof(f));
        printf("%d
",solve(S));

        scanf("%d",&n);    ///
    }
    return 0;
}