1271: 六度分离

http://tjuacm.chaosheng.top/problem.php?id=1271
http://acm.hdu.edu.cn/showproblem.php?pid=1869
https://vjudge.net/problem/HDU-1869

Dijkstra

算法解释：
https://blog.csdn.net/lbperfect123/article/details/84281300
代码参考：
https://blog.csdn.net/love20165104027/article/details/79706018

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 110;

int n, m;
int vis[N];
int dis[N];
int map[N][N];

void dij(int x){
    int pos = x, minn;
    memset(dis, 0, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    vis[pos] = 1;

    for(int i = 0; i < n; i++){
        if(pos != i) dis[i] = map[pos][i];
    }

    for(int i = 0; i < n - 1; i++){
        minn = INF;
        for(int j = 0; j < n; j++){
            if(!vis[j] && minn > dis[j]){
                minn = dis[j];
                pos = j;
            }
        }
        vis[pos] = 1;
        for(int j = 0; j < n; j++){
            //下面两种都可以 
//            if(!vis[j] && map[pos][j] < INF && (dis[pos] + map[pos][j] < dis[j])) 
//                dis[j] = dis[pos] + map[pos][j];
            if(!vis[j]) 
                dis[j] = min(dis[j], dis[pos] + map[pos][j]);
        }
    }
}

int main(){
    int a, b;
    while(cin >> n >> m){
        int f = 1;
        memset(map, 0x3f, sizeof(map));;
        for(int i = 1; i <= m; i++){
            cin >> a >> b;
            map[a][b] = map[b][a] = 1;
        }

        for(int i = 0; i < n; i++){
            dij(i);    
            for(int j = 0; j < n; j++){
                if(dis[j] - 1 > 6){
                    f = 0;
                    printf("No\n");
                    break;
                }
            }
            if(!f) break;
        }
        if(f) printf("Yes\n");
    }
    return 0;
}

BFS

参考：
http://www.javashuo.com/article/p-qweralmi-np.html

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 210;

int n, m;
int vis[N];
int dis[N];
int map[N][N];

bool bfs(int s, int v){
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    dis[s] = v; //起点距离赋值为 v(0);
    vis[s] = 1;
    q.push(s);

    while(q.size()){
        int f = q.front();
        q.pop();

        for(int i = 0; i < n; i++){
            if(map[f][i] == 1 && !vis[i]){   //vis=0表示这个点尚未访问过 mp!=0表示两个点能够直接访问.
                dis[i] = dis[f] + 1;          //这个点到起点的距离等于上个点的距离 +1
                vis[i] = 1;                 //标记访问过的点
                q.push(i);              //该点放入队列
            }
        }        
    }

    for(int i = 0; i < n; i++){
        if(dis[i] > 7) return false;        //距起点距离大于 5 说明不符合
    }
    return true;
}

int main(){
    int a, b;
    while(cin >> n >> m){
        int f = 1;
        memset(map, 0x3f, sizeof(map));;
        for(int i = 1; i <= m; i++){
            cin >> a >> b;
            map[a][b] = map[b][a] = 1;
        }

        for(int i = 0; i < n; i++){
            if(!bfs(i, 0)){
                f = 0;
                printf("No\n");
                break;
            }
        }
        if(f) printf("Yes\n");
    }
    return 0;
}