andyli

题解 UVA10917 【Walk Through the Forest】
首先求出从每个点$u$回家的最短路长度$d[u]$,则题目中的条件“存在一条从$B$出发回家的路径,比所有从$A$...
扫描右侧二维码阅读全文
24
2019/06

题解 UVA10917 【Walk Through the Forest】

首先求出从每个点$u$回家的最短路长度$d[u]$,则题目中的条件“存在一条从$B$出发回家的路径,比所有从$A$出发回家的路径都短”实际上是指$d[B]<d[A]$。这样,我们创建一个新的图,当且仅当$d[B]<d[A]$时加入有向边$A->B$,则题目的目标就是求出起点到终点的路径条数。因为这个图是$DAG$,可以用动态规划求解。
去除模板后代码如下:

const int INF = 0x3f3f3f3f, maxn = 1005;
class Dijkstra
{
  public:
    struct Edge
    {
        int from, to, dist;
        Edge(int u, int v, int d) : from(u), to(v), dist(d) {}
    };
    struct HeapNode
    {
        int d, u;
        bool operator<(const HeapNode &rhs) const
        {
            return d > rhs.d;
        }
    };
    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;
            done[u] = true;
            for (size_t 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});
                }
            }
        }
    }
};

bool G[maxn][maxn], G2[maxn][maxn];
int dp[maxn], n, m;

int dfs(int u)
{
    if (u == 0)
        return 1;
    if (dp[u] != -1)
        return dp[u];
    int ans = 0;
    for (int v = 0; v < n; v++)
        if (G2[v][u])
            ans += dfs(v);
    return dp[u] = ans;
}

int main()
{
    while (read(n), n)
    {
        read(m);
        Dijkstra dij;
        dij.init(n);
        memset(G, 0, sizeof(G));
        memset(G2, 0, sizeof(G2));
        memset(dp, -1, sizeof(dp));
        while (m--)
        {
            int u, v, w;
            read(u, v, w);
            --u, --v;
            dij.AddEdge(u, v, w);
            dij.AddEdge(v, u, w);
            G[u][v] = G[v][u] = true;
        }
        dij.dijkstra(1);
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (dij.d[j] < dij.d[i] && G[i][j])
                    G2[i][j] = true;
                else if (dij.d[i] < dij.d[j] && G[j][i])
                    G2[j][i] = true;
        writeln(dfs(1));
    }
    return 0;
}
Last modification:June 25th, 2019 at 11:28 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment