题解

Atcoder Beginner Contest 257 Problem F 题解

题目链接：_

题目大意

有$N$个城镇，分别编号$1，2，······，N$。

有$M$条路，第$i$条路连接城镇$U_i$和$V_i$。每条路都是双向的。路人甲经过一条路即从路的一边走到路的另一边需要$1$分钟。但对于一些道路，若其$U_i=0$，则代表该道路的一边即$U_i$不确定。

对于每一组$i=1,2,3,···,N$，试解答问题如下：

若不确定的边连接$i$，试求出点$1$到点$N$的最短距离，若点$1$与点$N$不联通，则输出$-1$。

样例输入1

3 2
0 2
1 2

样例输出1

-1 -1 2

样例解释1

如果所有的未确定道路都连接到城镇$1$，则道路$1$和道路$2$都连接了城镇$1$和$2$。是不可能从城镇$1$走到城镇$3$的。

如果所有的未确定道路都连接到城镇$2$，则道路$1$连接了$2$号城镇自己，道路$2$连接了城镇$1$和$2$，也是不可能从城镇$1$走到城镇$3$的。

如果所有的未确定道路都连接到城镇$3$，则道路$1$连接了城镇$2$和$3$，道路$2$连接了城镇$1$和$2$，于是可以从用$2$分钟城镇$1$走到城镇$3$：

• 走道路$2$，用$1$分钟从城镇$1$走到城镇$2$。
• 走道路$1$，用$1$分钟从城镇$2$走到城镇$3$。

因此输出为 $-1 \quad -1 \quad 2$。
请注意，确定了不确定的道路连接到的城镇，可能有一条道路连接城镇和城镇本身，也可能有多条道路连接同一对城镇。

样例输入2

5 5
1 2
1 3
3 4
4 5
0 2

样例输出2

3 3 3 3 2

解析

该题为一道图论题。
设点$0$与点$i$相连，U_i=j，则连接此二点后点$1$到点$N$的最短路径会有发生改变即经过路径$(i,j)$和不发生改变即不经过路径$(i,j)$两种情况。若经过路径$(i,j)$，则有两种经过的可能，即：从点$i$进入再从点$j$离开和从点$j$进入再从点$i$离开，如图所示：

因此，我们可以先使用广度优先搜索算法求出点$1$与点$N$到任意点的距离，注意：包括点$0$。然后枚举每一个点，从而计算出点$1$到点$N$经过路径$(i,j)$的最短距离即经过路径$(i,j)$且从点$i$进入再从点$j$离开的最短距离与经过路径$(i,j)$且从点$j$进入再从点$i$离开的最短距离即$dis start 1[U_i]+dis start N[i]$与$dis start 1[i]+dis start N[U_i]$的最小值，再将其与不经过路径$(i,j)$的点$1$到$N$的最短距离比较，求出二者最大值即可。

代码实现

以上算法代码实现如下：

#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define M 300005
typedef long long ll;
using LL=long long;
#define INF 0x3f3f3f3f
int dis_to_1[N],dis_to_N[N];
int n,m;
struct node{
  int to;
};
vector<node>q[N];
void gdyxss_start_1(){
  bool vis[N];
  memset(vis,false,sizeof vis);
  memset(dis_to_1,INF,sizeof dis_to_1);
  queue<int>p;
  p.push(1);
  vis[1]=true;
  dis_to_1[1]=0;
  while(!p.empty()){
    int u=p.front();
    p.pop();
    for(int i=0;i<q[u].size();i++){
      int v=q[u][i].to;
      if(!vis[v]){
        dis_to_1[v]=dis_to_1[u]+1;
        vis[v]=1;
        p.push(v);
      }
    }
  }
}
void gdyxss_start_N(){
  bool vis[N];
  memset(vis,false,sizeof vis);
  memset(dis_to_N,INF,sizeof dis_to_N);
  queue<int>p;
  p.push(n);
  vis[n]=true;
  dis_to_N[n]=0;
  while(!p.empty()){
    int u=p.front();
    p.pop();
    for(int i=0;i<q[u].size();i++){
      int v=q[u][i].to;
      if(!vis[v]){
        dis_to_N[v]=dis_to_N[u]+1;
        vis[v]=1;
        p.push(v);
      }
    }
  }
}
int main(){
  std::ios::sync_with_stdio(0);
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    int u,v;
    cin>>u>>v;
    q[u].push_back({v});
    q[v].push_back({u});
  }
  gdyxss_start_1();
  gdyxss_start_N();
    for(int i=1;i<=n;i++){
        int res=min(dis_to_1[0]+dis_to_N[i],dis_to_1[i]+dis_to_N[0]);
        res=min(res,dis_to_1[n]);
        if(res==INF) cout<<"-1"<<' ';
        else cout<<res<<" ";
    }
  return 0;
}

注：以上代码使用动态数组存储图。

另附使用链表存储图代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,INF=0x3f3f3f3f; //INF表示正无穷，即两边不可到达
int n,m;
int he[N],ne[N<<1],go[N<<1],val[N<<1],tot; //前向星
int vis[N],dis1[N],disn[N]; //vis为标记数组，dis1和disn分别表示从1和n开始的dis值
inline void add(int a,int b,int c){
    ne[++tot]=he[a];he[a]=tot;go[tot]=b;val[tot]=c;
} //加边
inline void bfs(int s,int *dis){
    memset(vis,0,sizeof vis);
    dis[s]=0; 
    queue<int>q;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=he[u];i;i=ne[i]){
            int v=go[i];
            if(!vis[v]){
                q.push(v);vis[v]=1;
                dis[v]=dis[u]+val[i]; //计算dis
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v,1);add(v,u,1);
    }
    memset(dis1,INF,sizeof dis1);
    memset(disn,INF,sizeof disn); //开始时全不可达
    bfs(1,dis1);
    bfs(n,disn); //bfs找到dis值
    for(int i=1;i<=n;i++){
        int ans=min(dis1[n],min(dis1[0]+disn[i],dis1[i]+disn[0])); //具体见图
        if(ans==INF) cout<<-1<<" "; //如果不可达
        else cout<<ans<<" ";
    }
    return 0;
}

版权声明

本文样例解释1及使用链表存储图代码来源于彭震楠的题解，本文未经作者允许，不得随意转载，非商业转载需注明出处。