题解 P1144 【最短路计数】

· · 题解

看到题解区的很多大佬用的是分层建图，然后跑一边最短路就OK了

然而蒟蒻却想不到这种做法....

首先，看到题目，我们要先想到——暴力！

暴力无疑是很好写的了，用SPFA/Dijkstra/BFS 预处理跑一边最短路，然后爆搜记录最 短路条数。

写了大概十分钟，交了上去（还挣扎一下，开个氧气。

代码如下:

#include <bits/stdc++.h>
#define inf 0x7fffffff
using namespace std;
const int maxn = 2000005;
const int mod = 100003;
int ans[maxn];
int n,m,head[maxn],cnt,dis[maxn],dp[maxn];
bool inq[maxn],vis[maxn];

struct edge{
    int to,nxt;
}e[maxn];

void add(int u,int v)
{
    e[++cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

void SPFA()
{
    priority_queue <pair<int,int> > q;
    for(int i=2 ;i<=n;++i) dis[i] = inf;
    q.push(make_pair(0,1));
    inq[1] = 1;
    while(!q.empty())
    {
        int now = q.top().second;
        q.pop();
        inq[now] = 0;
        for(int i = head[now];i;i = e[i].nxt)
        {
            int to = e[i].to;
            if(dis[to] > dis[now] + 1)
            {
                dis[to] = dis[now] + 1;
                q.push(make_pair(-dis[to],to));
                inq[to] = 1;
            }
        }
    }
    //for(int i=1;i<=n;++i) printf("dis[%d] is %d\n",i,dis[i]);
}

void DFS(int now,int sum)
{
    ans[now] ++;
    for(int i=head[now];i;i=e[i].nxt)
    {
        int to = e[i].to;
        if(sum + 1 == dis[to])
         DFS(to,sum + 1);
    }
}

int main ()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);  
    }
    SPFA();
    DFS(1,0);
    for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}

我们思考优化。

这份代码的瓶颈在DFS部分，导致复杂度到了O(2^N + KE)

其中 KE 为SPFA 复杂度， 2^N 为DFS复杂度。

很显然了，我们要对DFS进行优化。

基于图论的DFS，我们可以通过 记忆化搜索 或者 DP 进行优化。

我们这里选择使用DP。

考虑一种DP。

设计转移方程 为： 若 $A$ 与 $B$ 之间连了一条边 且 $A$ 的深度小于 $B$ 的深度 则 $DP[B] += DP[A]

1.最优子结构

从图的层次来说，每个节点只需要进行一次遍历出边的松弛操作，就可以找到所有最短路的条数。

可以用反证法证明，如果需要一个节点入队多次，后面的节点深度一定是大于等于前面节点的深度，则一定会更劣，也就是说没有入队的必要。

由此证得。

2.无后效性

如果当前便利的节点为A , 我们遍历到了一条他的出边指向 B

则就让 B 的 最短路条数 += A 的最短路条数， 且与A的最短路从何而来无关。

有了这些，代码就很好实现了。

注意函数

void DP()

完整代码如下:

#include <bits/stdc++.h>
#define inf 0x7fffffff
using namespace std;
const int maxn = 2000005;
const int mod = 100003;
int n,m,head[maxn],cnt,dis[maxn],dp[maxn];
bool inq[maxn],vis[maxn];

struct edge{
    int to,nxt;
}e[maxn];

void add(int u,int v)
{
    e[++cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

void SPFA()
{
    priority_queue <pair<int,int> > q;
    for(int i=2 ;i<=n;++i) dis[i] = inf;
    q.push(make_pair(0,1));
    inq[1] = 1;
    while(!q.empty())
    {
        int now = q.top().second;
        q.pop();
        inq[now] = 0;
        for(int i = head[now];i;i = e[i].nxt)
        {
            int to = e[i].to;
            if(dis[to] > dis[now] + 1)
            {
                dis[to] = dis[now] + 1;
                q.push(make_pair(-dis[to],to));
                inq[to] = 1;
            }
        }
    }
    //for(int i=1;i<=n;++i) printf("dis[%d] is %d\n",i,dis[i]);
}

void DP()
{
    memset(vis,0,sizeof(vis));
    queue <int> q;
    q.push(1);dp[1]=1;vis[1]=1;dis[1]=0;
    while(!q.empty())
    {
        int now = q.front();q.pop();
        for(int i=head[now];i;i=e[i].nxt)
        {
            int to = e[i].to;
            if(dis[to] == dis[now] + 1)
            {
                dp[to] += dp[now];
                dp[to] %= mod;
                if(!vis[to])
                    q.push(to),vis[to] = 1;
            }
        }
    }
}

int main ()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);  
    }
    SPFA();
    DP();
    for(int i=1;i<=n;++i) printf("%d\n",dp[i]);
    return 0;
}