题解 P1144 【最短路计数】

· · 题解

想必大家都会求最短路吧，这里就不再多说了；

我看有很多人在一顿套模板，什么dijkstra,SPFA等等,这是可以的；

但身为OIer，思路要开阔对不对？

首先我们注意到，我们可以利用bfs来求每个点的深度。因为在所有边边权为1的时候，点的深度就是点的最短距离；

这样在写法上便少了队列优化SPFA中退栈时还要把标记抹除这一操作，会大大提高算法速度；

在bfs的时候，我们不仅仅要从一个点的父亲继承最短路，还要继承方案数；

有个细节，起点的方案数要记为1；

#include <bits/stdc++.h>
#define int long long
#define p 100003
using namespace std;
struct littlestar{
    int to;
    int nxt;
}star[4000010];
int head[4000010],cnt;
inline void add(register int u,register int v)
{
    star[++cnt].to=v;
    star[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,m;
long long g[1000010];
int dis[1000010],vis[1000010];
queue<int> q;
int st,ed;
inline void bfs(register int s)
{
    memset(g,0,sizeof(g));
    memset(dis,0x3f,sizeof(dis));
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    g[s]=1;
    while(q.size()){
        register int u=q.front();
        q.pop();
        for(register int i=head[u];i;i=star[i].nxt){
            register int v=star[i].to;
            if(dis[v]==dis[u]+1) g[v]=(g[u]+g[v])%p;
            if(vis[v]) continue;
            vis[v]=1;
            dis[v]=dis[u]+1;
            g[v]=g[u]%p;
            q.push(v);
        }
    }
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(register int i=1;i<=m;i++){
        register int u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v);
        add(v,u);
    }
    bfs(1);
    for(int i=1;i<=n;i++){
        printf("%lld\n",g[i]);
    }
}

有闲时间的读者可以看一下这道题的扩展：

一张N*M的无向图，有k个特殊的点；你从1号点出发，必须停留且只停留在一个特殊点休息一段时间，然后到达n号点；(可以一次经过多个特殊点，但如果在不同的特殊点停留休息，就算不同种方案)；求符合条件的最短路的方案数；

其实这道题稍加思考就可以得到正解：分别从1号点和n号点bfs()求出每个点到1号点和n号点的最短路及最短路下的方案数；我们根据乘法原理把最短路下的方案数乘起来就可以了；

#include <bits/stdc++.h>
#define int long long
#define p 1000000007
using namespace std;
struct littlestar{
    int to;
    int nxt;
}star[8000010];
int head[8000010],cnt;
void add(int u,int v)
{
    star[++cnt].to=v;
    star[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,m;
char s[1010][1010];
int query[1010][1010];
long long g[1000010];
int water[1000010];
int dis[1000010],vis[1000010];
queue<int> q;
int st,ed;
void bfs(int s)
{
    memset(g,0,sizeof(g));
    memset(dis,0x3f,sizeof(dis));
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    g[s]=1;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=star[i].nxt){
            int v=star[i].to;
            if(dis[v]==dis[u]+1) g[v]=(g[u]+g[v])%p;
            if(vis[v]) continue;
            vis[v]=1;
            dis[v]=dis[u]+1;
            g[v]=g[u]%p;
            q.push(v);
        }
    }
}
int stdis[1000010];
long long stg[1000010];
signed main()
{
    scanf("%lld%lld",&n,&m);
    int num=0;
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=m;j++){
            query[i][j]=++num;
        }
    }
    for(register int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
    }   
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=m;j++){
            if(s[i][j]=='@') st=query[i][j];
            if(s[i][j]=='#') ed=query[i][j];
            if(s[i][j]=='*') water[++water[0]]=query[i][j];
            if(s[i][j]=='X') continue;
            if(i-1>0&&s[i-1][j]!='X'){
                add(query[i][j],query[i-1][j]);
            }
            if(j-1>0&&s[i][j-1]!='X'){
                add(query[i][j],query[i][j-1]);
            }
            if(i+1<=n&&s[i+1][j]!='X'){
                add(query[i][j],query[i+1][j]);
            }
            if(j+1<=m&&s[i][j+1]!='X'){
                add(query[i][j],query[i][j+1]);
            }
        }
    }
    bfs(st);
    for(int i=1;i<=num;i++) stdis[i]=dis[i],stg[i]=g[i];
    memset(vis,0,sizeof(vis));
    bfs(ed);
    int ans=INT_MAX;
    for(int i=1;i<=water[0];i++){
        ans=min(ans,stdis[water[i]]+dis[water[i]]);
    }
    long long fians=0;
    for(int i=1;i<=water[0];i++){
        if(stdis[water[i]]+dis[water[i]]==ans){
            fians=(fians+stg[water[i]]*g[water[i]]%p)%p;
        }
    }
    if(ans==INT_MAX){
        cout<<"-1 0";
        return 0;
    }
    cout<<ans<<" "<<fians;
}
/*
3 3
@..
.*.
*.#

4 4
@...
....
....
...#

*/