HDU 5876 补图最短路

雨点打透心脏的1/2处 2023-06-05 15:00 9阅读 0赞

## 题意：给一个图，和起点s，求s在补图中到各个点的最短路。 ##

## 分析：补图最短路，算是比较套路的一类题了，bfs+两个set维护邻接点和未扩展的点。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define inf 0x3f3f3f3f
    const int N = 1e6+5;
    int t,n,m,s,d[N];
    vector<int> g[N];
    
    void bfs() {
        queue<int> q;
        q.push(s);
        d[s] = 0;
        set<int> a,b;
        for(int i=1;i<=n;i++) a.insert(i);
        a.erase(s);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(auto v:g[u]) {
                if(!a.count(v)) continue;
                b.insert(v);///未扩展的点
                a.erase(v);///邻接点
            }
            for(auto it:a) {
                d[it] = d[u] + 1;
                q.push(it);
            }
            a = b;
            b.clear();
        }
        int f=0;
        for(int i=1;i<=n;i++) {
            if(i==s) continue;
            if(d[i]==inf) d[i] = -1;
            if(f) printf(" %d",d[i]);
            else printf("%d",d[i]);
            f=1;
        }
        printf("\n");
    }
    
    int main(){
        while(~scanf("%d",&t)) {
            while(t--) {
                scanf("%d%d",&n,&m);
                for(int i=1;i<=n;i++) g[i].clear(),d[i]=inf;
                for(int i=1;i<=m;i++) {
                    int u,v;
                    scanf("%d%d",&u,&v);
                    g[u].push_back(v);
                    g[v].push_back(u);
                }
                scanf("%d",&s);
                bfs();
            }
        }
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 5876 补图最短路

题意：给一个图，和起点s，求s在补图中到各个点的最短路。分析：补图最短路，算是比较套路的一类题了，bfs+两个set维护邻接点和未扩展的点。代码：

雨点打透心脏的1/2处/ 2023年06月05日 15:00/ 0 赞/ 10 阅读

相关 hdu 5521 图论最短路

Meeting Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K

我会带着你远行/ 2022年08月10日 03:54/ 0 赞/ 28 阅读

相关 hdu 1839 二分搜索+dijkstra最短路

[点击打开链接][Link 1] 题意: 给定一个无向图, 顶点从1-n, 给定m条边, 每条边有两个值, 一是这条边的最大容量, 二是经过这条边需要的时间, 要求从1顶点开

小灰灰/ 2022年07月28日 00:23/ 0 赞/ 168 阅读

相关 HDU - 2544 - 最短路

-------------------- 题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=2544][http_acm.hdu

系统管理员/ 2022年06月12日 10:38/ 0 赞/ 191 阅读

相关图论-最短路

单源最短路：单元最短路问题是固定一个起点，求它到其他所有点的最短路的问题。终点固定的问题也叫单源最短路。算法1：Bellman-Ford算法记从起点s出发到顶点i的

小鱼儿/ 2022年05月28日 02:05/ 0 赞/ 189 阅读

相关 HDU_2544最短路最短路的模板

最短路 Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

以你之姓@/ 2022年05月24日 22:54/ 0 赞/ 197 阅读

相关 HDU - 2544 最短路

最短路 Problem Description 在每年的校赛里，所有进入决赛

╰+哭是因爲堅強的太久メ/ 2022年05月19日 12:34/ 0 赞/ 236 阅读

相关最短路径(Dijkstra)-HDU 2544-最短路

最短路径(Dijkstra)-HDU 2544-最短路 -------------------- 题目链接： [最短路][Link 1]

亦凉/ 2022年05月14日 03:38/ 0 赞/ 232 阅读

相关 HDU - 5521 巧妙地最短路

题意：n个点，m块，块的意思就是说，在块中的点任意两点的距离都是t，问分别从1点和n点走到某个点，这个点的花费就是二者较大的，问这n个点花费最小是多少，并按字典序打印序号思

迷南。/ 2022年05月08日 08:38/ 0 赞/ 162 阅读

相关 HDU 2544 最短路

最短路时间限制：5000/1000 MS（Java / Others）内存限制：32768/32768 K（Java /其他）提交总数：106773接受提交内容：

桃扇骨/ 2021年10月18日 08:20/ 0 赞/ 344 阅读