题解 P3906 【Geodetic集合】

· · 题解

这道题算是一个最短路的水题了，然而难度是提高+/省选-？

先说说这题的思路：

  1. 先读入一个图的顶点数n和边数m，再读入每个边的信息（起点，终点），把它们存储起来，这里我用的邻接表存储法（当然也可以用邻接矩阵存储）。
  2. 接下来开始读入问题（也是整个程序的核心），读入v,u。先用spfa单源最短路径算出v点到其他点的最短距离，用d数组存储（SPFA模板不阐述）。然后再用spfa算出u点到其他点的最短距离，用d2数组存储。算完最短距离后开始遍历每个点，如果这个点到v的最短路径加上这个点到u的最短路径恰好等于v到u的最短距离，那么就输出这个点的编号。

思路就这么多，十分简单。

下面有请可爱的代码君上场qwq

注意:减少代码复制，共创美好洛谷！

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <cstdio>
#include <cstring>  //头文件 
using namespace std;
struct node{
    int to,cost;
};
vector<node> G[110];//vector数组，邻接表存储 
int d[110],d2[110];//d数组存的是v点到其他点的最短距离，d2数组存的是u点到其他点的最短距离 
bool used[110];
int n,m,x;
stack<int>s;
inline int read()//读入优化 
{
    int n=0;
    char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9')
     {
         n=n*10+ch-'0';
         ch=getchar();
     }
    return n; 
}
void spfa(int s)//SPFA模板 
{
    queue<int>q;
    fill(d+1,d+n+1,100000000);//一开始要初始化一个很大的数 
    fill(used+1,used+n+1,false);
    d[s]=0;
    used[s]=true;
    q.push(s);
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        used[v]=false;
        for(int i=0; i<G[v].size(); i++)
        {
            node e=G[v][i];
            if(d[v]+e.cost<d[e.to])
            {
                d[e.to]=d[v]+e.cost;
                if(!used[e.to])
                {
                    q.push(e.to);
                    used[e.to]=true;
                }
            }
        }
    }
}
void spfa2(int s)//同样是模板 
{
    queue<int>q;
    fill(d2+1,d2+n+1,100000000);
    fill(used+1,used+n+1,false);
    d2[s]=0;
    used[s]=true;
    q.push(s);
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        used[v]=false;
        for(int i=0; i<G[v].size(); i++)
        {
            node e=G[v][i];
            if(d2[v]+e.cost<d2[e.to])
            {
                d2[e.to]=d2[v]+e.cost;
                if(!used[e.to])
                {
                    q.push(e.to);
                    used[e.to]=true;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);//读入 
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        a=read(),b=read();//读入 
        G[a].push_back((node){b,1});//邻接表存储法，注意权值要为1 
        G[b].push_back((node){a,1});
    }
    int q;
    cin>>q;//读入问题的数量 
    while(q--)
    {
        int v,u;
        cin>>v>>u;
        spfa(v);
        spfa2(u);//SPFA大法好 
        for(int i=1; i<=n; i++)
        if(d[i]+d2[i]==d[u]) cout<<i<<' ';//如果第i点到v的最短路径加上到u的最短路径恰好等于d[u]，那么就输出i
        cout<<endl;//换行 
    }
    return 0;//就这样完美的结束 
}

p.s 本人蒟蒻一枚，如果此题解有地方说的不好或是说错了，请在评论区告诉错误原因，谢谢！如果您认为这篇题解不错，就请话1秒钟的时间点个赞吧！