0基础刷图论最短路 1（从ATcoder 0分到1800分）

2024-04-12 09:52
文章标签 基础 图论 短路 atcoder 1800 分到

本文主要是介绍0基础刷图论最短路 1（从ATcoder 0分到1800分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

ATC最短路1 （本文难度rated 0~ 1000）

题目来源：Atcoder
题目收集：
https://atcoder-tags.herokuapp.com/tags/Graph/Shortest-Path
（里面按tag分类好了Atcoder的所有题目，类似cf）
（访问需要魔法）
这算是一个题单，各位有兴趣可以按照这个顺序来刷。
我的代码仅供参考。
会提示关键性质和步骤。 部分有注释。
洛谷、知乎、可以搜到题解。

文章目录

  • ATC最短路1 （本文难度rated 0~ 1000）
    • 1-**Hands**
    • 2- **Cat Snuke and a Voyage**
    • 3-**Collision** https://atcoder.jp/contests/abc209/tasks/abc209_d
    • 4-**友達の友達**
    • **5-Line++**
    • 6-**Range Flip Find Route**
    • 7- Wall
    • 8-**Our clients, please wait a moment**

1-Hands

https://atcoder.jp/contests/arc109/tasks/arc109_a

思维 / 最短路板子(一道atc的负分题)

这题比下面那些800多的难多了…

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18void slove(){int a,b,x,y;cin>>a>>b>>x>>y;int ans = 0;if(a>b){if(2*x>=y){ //如果直接下楼更方便：ans = (a-b-1)*y + x;}else{ans = (a-b-1)*2*x + x;}}else if(a==b){ans = x;}else{if(2*x>=y){ans = (b-a)*y+x;}else{ans = (b-a)*2*x+x;}}cout<<ans<<endl;
}signed main(){slove();
}

2- Cat Snuke and a Voyage

https://atcoder.jp/contests/abc068/tasks/arc079_a

最短路

弱智题…这种题在atc里居然 rate 609？？？？

最短路都不需要跑…

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18void slove(){int n,m;cin>>n>>m;vector<vector<int>> g(n+1);for(int i=1;i<=m;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}for(auto i:g[1]){for(auto j:g[i]){if(i==n or j==n){cout<<"POSSIBLE"<<endl;return;}}}cout<<"IMPOSSIBLE"<<endl;
}signed main(){slove();
}

3-Collision https://atcoder.jp/contests/abc209/tasks/abc209_d

思维

有点意思

/*
当两个城镇的距离是偶数，说明是在城镇相遇
否则在半路相遇。问题是，如何求出任意两个城镇的距离？
这个问题，在N = 1e5的时候是无解的。所以，我们考虑，如何知道这两个城镇的最短距离是否为偶数？
(一个很重要的能力：根据数据范围判断算法)
(树图常见操作：染色)这个问题可以转换为：
对于每个点，我们给与其相邻的所有点涂上不同的颜色。
因为相邻的话，距离是1，是奇数。然后任意两个点，我们只需要观察是否为同一颜色。
如果它们是同一颜色，说明间距是偶数。*/#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18
const int N = 1e5+7;vector<vector<int>> g(N);
int color[N];void get_color(int u,int fa){for(auto v:g[u]){if(v==fa)continue;color[v] = 1 - color[u];get_color(v,u);}
}
void slove(){int n,q;cin>>n>>q;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}get_color(1,-1);while(q--){int u,v;cin>>u>>v;if(color[u]==color[v])cout<<"Town"<<endl;else cout<<"Road"<<endl;}
}signed main(){slove();
}

4-友達の友達

https://atcoder.jp/contests/abc016/tasks/abc016_3

这特么跟最短路有什么关系。

这不是暴力吗？

/*
找到每个点朋友的朋友个数。一共有N个人。对于1.
我们需要标记1的所有儿子。
然后再从1的第一个儿子开始，遍历1的第一个儿子的所有儿子
如果没被标记，那么标记，答案+1然后1算完了话，再重新清空标记，去计算2N<10*/#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18
int n,m;
vector<vector<int>> g(11);
int f[11];
void todo(int id){vector<int> flag(n+1);for(auto v:g[id]){flag[v]=1;}for(auto v:g[id]){for(auto k:g[v]){if(k==id)continue;if(flag[k])continue;flag[k]=1;f[id]++;}}
}void slove(){cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}for(int i=1;i<=n;i++){todo(i);}for(int i=1;i<=n;i++){cout<<f[i]<<endl;}
}signed main(){slove();
}

5-Line++

https://atcoder.jp/contests/abc160/tasks/abc160_d

水题

/*
给定一个图。
有N个顶点
每个i = 1，2...,N-1 ，都有 i 与 i+1 连一条边。也就是，这其实是一条链子。然后我们在选两个点，x，y
在他们之间连接一个边。现在问你在这幅图中，任意(i,j)之间的最短距离为k的整数对有多少？K取遍1~n-1N的取值范围是 1e3,所以我们可以n^2 求解每两个点之间的距离。所以，任意两个点之间的距离：
1、走直道： j-i
2、走弯道： |x-i| + 1 +|j-y|*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18
const int N = 2e3+7;
int box[N];
void slove(){int n,x,y;cin>>n>>x>>y;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){int dist = min(abs(j-i),abs(i-x)+1+abs(j-y));box[dist]++;}}for(int i=1;i<=n-1;i++){cout<<box[i]<<endl;}}signed main(){slove();
}

6-Range Flip Find Route

https://atcoder.jp/contests/agc043/tasks/agc043_a

数字三角形模型dp

这严格意义上不是一道图论，而是一道dp。但是我在刷图论的时候遇到了，那就放过来。

这道题，说的是我们每一次操作可以选择一个任意大小的矩形(最小是1)，然后将这里面的所有颜色反转。

而且每次我们只能往下走/往右走。所以引发我想起这个模型。

思考什么时候需要反转？

当$ a[i][j]==a[i-1][j] \ or \ a[i][j]==a[i][j-1] $的时候

我们的翻转次数是与上一个状态一样的。

当 a [ i ] [ j ] = = ′ . ′ a[i][j]=='.' a[i][j]==′.′的时候，这个点是不需要反转的，所以反转次数与上一个状态一样。

其他的情况，就需要反转次数+1

然后就是先处理下边界，我因为这个WA了几次

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18int dp[101][101];
char a[101][101];void slove(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];dp[1][1]=(a[1][1]=='#');for(int i=2;i<=n;i++){if(a[i][1]=='.' or a[i][1]==a[i-1][1]) dp[i][1]=dp[i-1][1];else dp[i][1] = dp[i-1][1]+1;}for(int j=2;j<=m;j++){if(a[1][j]=='.' or a[1][j]==a[1][j-1])dp[1][j]=dp[1][j-1];else dp[1][j] = dp[1][j-1]+1;}for(int i=2;i<=n;i++){for(int j=2;j<=m;j++){int tempu = dp[i-1][j]+1;int templ = dp[i][j-1]+1;if(a[i][j]=='.'){tempu = dp[i-1][j];templ = dp[i][j-1];}if(a[i][j]==a[i-1][j]){tempu = dp[i-1][j];}if(a[i][j]==a[i][j-1]){templ = dp[i][j-1];}dp[i][j]=min(templ,tempu);}}cout<<dp[n][m]<<endl;
}signed main(){slove();
}

7- Wall

https://atcoder.jp/contests/abc079/tasks/abc079_d

dijkstra / floyed

思考一个问题：当 i->j 的路径长度 不等于 j-> i 的路径长度的时候。
还能用dijkstra吗可以，不过我们要搞清楚，题目需要我们从谁走到谁？如果是求从起点到起点以外的点，那么我们正向跑一边dijkstra是没问题的。如果是要求别的点，走到起点。
那么显然我们可以通过建立反向图，再从起点跑一边dijkstra通过这个问题，我们可以发现，dij算法是不会“回头的”因为我们通过最小堆的优化，每次拓展的点都是离当前点最近的一点。
如果回头的话，就说明，从u到v，有更短的距离
也就是说，从u走别的路有更短的距离到v
例如 u -> i -> j -> v
那么，i,j 一定会比v先更新。
并且，在他们更新之后，只会通过这条路更新v，不会通过 u->v 更新v
所以，不会回头。

Dijkstra 算法

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18int n,m;
int dist[10];
int c[10][10];
int a[201][201];
bool flag[10];
void dijkstra(){for(int i=0;i<=9;i++)dist[i]=INF;priority_queue<PII,vector<PII>,greater<PII>> q;dist[1]=0;q.push({0,1});while(q.size()){int u = q.top().second;q.pop();if(flag[u])continue;flag[u]=1;for(int i=0;i<=9;i++){if(i==u)continue;if(dist[i]>dist[u]+c[i][u]){dist[i] = dist[u]+c[i][u];q.push({dist[i],i});}}}int ans = 0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]!=-1)ans+=dist[a[i][j]];}}cout<<ans<<endl;
}
void slove(){cin>>n>>m;for(int i=0;i<=9;i++){for(int j=0;j<=9;j++){cin>>c[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}dijkstra();}signed main(){slove();
}

floyd做法

做法2，floyed做法
用于求出当n较小的时候，图中任意两点的最小距离
时间复杂度O(n^3)有个问题就是，为什么枚举中间点的循环是放在最外面?我们的循环是这样的：for(int k=0;k<=9;k++){for(int i=0;i<=9;i++){for(int j=0;j<=9;j++){dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);}}}如果k放在外层，k是从小到达逐渐增长的。可以发现：dist[i][k]一定在dist[i][j]之前被更新过，dist[k][j]一定在dist[i][j]之前被更新过比如说，k=3 ， 而在k=0的时候，所有的dp[i][j]都被更新过一次了。我们使用的都是目前最优秀的状态。如果把k放在里面：for(int i=0;i<=9;i++){for(int j=0;j<=9;j++){for(int k=0;k<=9;k++){dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);}}}显然，当i,j都很小的时候,k已经可以跑到9了。所以 dp[i][k] 并不会在 dp[i][j]被更新前更新。/*
把网格里面，除了-1以外的所有数
转化为1所需要的最小代价之和为多少。已经给了
如果把  i 转化为 j 的最小代价是 c[i][j]只需要跑一边最短路。
求出 i转化为1的最短路即可。*/#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18int dist[10][10];
int n,m;
int a[201][201];
bool flag[201];void slove(){cin>>n>>m;for(int i=0;i<=9;i++){for(int j=0;j<=9;j++){cin>>dist[i][j];}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];//floyedfor(int k=0;k<=9;k++){for(int i=0;i<=9;i++){for(int j=0;j<=9;j++){dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);}}}int ans =0 ;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]!=-1){//求和ans+=dist[a[i][j]][1];}}}cout<<ans<<endl;}signed main(){slove();
}

8-Our clients, please wait a moment

https://atcoder.jp/contests/abc325/tasks/abc325_e

一点小思考：

有个想法：
dijkstra是求起点到所有点的最短路。那么为什么i,j的最短路不能等于
dist[j] - dist[i] 呢？
很显然的问题就是，1到j的最短路不一定经过i
如果经过i，那么这就是ok的。
/*
有N个城市
你现在要从城市1到达城市N对于城市i和城市j
可以选择乘坐汽车：花费时间：D[i][j]*A
乘坐火车 花费时间：D[i][j]*B+C对于汽车，你可以在半途中，用汽车换成火车。
但是不能由火车换成汽车。一个很简单的办法就是：先求出一遍只乘坐公车的最短路。
然后枚举每个点，开始坐火车。我们还需要去算一遍，火车的最短路。由于此时的边权是对称的。所以，我们可以从n点出发
这样可以算出火车的dist2[i]然后二者相加： dist1[i]+dist[2] =  最短距离*/#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18int n,a,b,c;
int d[1001][1001];
int dist[1001];
int dist2[1001];
bool flag[1001];void dijkstra(){for(int i=0;i<=n;i++)dist[i]=INF;dist[1]=0;priority_queue<PII,vector<PII>,greater<PII>> q;q.push({0,1});while(q.size()){int u = q.top().second;q.pop();if(flag[u])continue;flag[u]=1;for(int i=1;i<=n;i++){if(i==u)continue;int w = d[u][i]*a;if(dist[i]>dist[u]+w){dist[i] = dist[u] + w;q.push({dist[i],i});}}}memset(flag,0,sizeof flag);for(int i=0;i<=n;i++)dist2[i]=INF;dist2[n]=0;priority_queue<PII,vector<PII>,greater<PII>> q2;q2.push({0,n});while(q2.size()){int u = q2.top().second;q2.pop();if(flag[u])continue;flag[u]=1;for(int i=1;i<=n;i++){if(i==u)continue;int w = d[u][i]*b+c;if(dist2[i]>dist2[u]+w){dist2[i] = dist2[u] + w;q2.push({dist2[i],i});}}}int ans = INF ;for(int i=1;i<=n;i++){ans = min(ans,dist[i]+dist2[i]);}cout<<ans<<endl;}void slove(){cin>>n>>a>>b>>c;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>d[i][j];}}dijkstra();
}signed main(){slove();
}

这篇关于0基础刷图论最短路 1（从ATcoder 0分到1800分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/896801。

相关文章

从基础到高级详解Python数值格式化输出的完全指南

从基础到高级详解Python数值格式化输出的完全指南

《从基础到高级详解Python数值格式化输出的完全指南》在数据分析、金融计算和科学报告领域,数值格式化是提升可读性和专业性的关键技术,本文将深入解析Python中数值格式化输出的相关方法,感兴趣的小伙... 目录引言：数值格式化的核心价值一、基础格式化方法1.1 三种核心格式化方式对比1.2 基础格式化示例
阅读更多...
redis-sentinel基础概念及部署流程

redis-sentinel基础概念及部署流程

《redis-sentinel基础概念及部署流程》RedisSentinel是Redis的高可用解决方案,通过监控主从节点、自动故障转移、通知机制及配置提供,实现集群故障恢复与服务持续可用,核心组件包... 目录一. 引言二. 核心功能三. 核心组件四. 故障转移流程五. 服务部署六. sentinel部署
阅读更多...
从基础到进阶详解Python条件判断的实用指南

从基础到进阶详解Python条件判断的实用指南

《从基础到进阶详解Python条件判断的实用指南》本文将通过15个实战案例,带你大家掌握条件判断的核心技巧,并从基础语法到高级应用一网打尽,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录​引言：条件判断为何如此重要一、基础语法：三行代码构建决策系统二、多条件分支：elif的魔法三、
阅读更多...
Python WebSockets 库从基础到实战使用举例

Python WebSockets 库从基础到实战使用举例

《PythonWebSockets库从基础到实战使用举例》WebSocket是一种全双工、持久化的网络通信协议,适用于需要低延迟的应用,如实时聊天、股票行情推送、在线协作、多人游戏等,本文给大家介... 目录1. 引言2. 为什么使用 WebSocket？3. 安装 WebSockets 库4. 使用 We
阅读更多...
从基础到高阶详解Python多态实战应用指南

从基础到高阶详解Python多态实战应用指南

《从基础到高阶详解Python多态实战应用指南》这篇文章主要从基础到高阶为大家详细介绍Python中多态的相关应用与技巧,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、多态的本质：python的“鸭子类型”哲学二、多态的三大实战场景场景1：数据处理管道——统一处理不同数据格式
阅读更多...
MySQL数据类型与表操作全指南( 从基础到高级实践)

MySQL数据类型与表操作全指南( 从基础到高级实践)

《MySQL数据类型与表操作全指南(从基础到高级实践)》本文详解MySQL数据类型分类（数值、日期/时间、字符串）及表操作（创建、修改、维护）,涵盖优化技巧如数据类型选择、备份、分区,强调规范设计与... 目录mysql数据类型详解数值类型日期时间类型字符串类型表操作全解析创建表修改表结构添加列修改列删除列
阅读更多...
Python 函数详解:从基础语法到高级使用技巧

Python 函数详解:从基础语法到高级使用技巧

《Python函数详解:从基础语法到高级使用技巧》本文基于实例代码,全面讲解Python函数的定义、参数传递、变量作用域及类型标注等知识点,帮助初学者快速掌握函数的使用技巧,感兴趣的朋友跟随小编一起... 目录一、函数的基本概念与作用二、函数的定义与调用1. 无参函数2. 带参函数3. 带返回值的函数4.
阅读更多...
python panda库从基础到高级操作分析

python panda库从基础到高级操作分析

《pythonpanda库从基础到高级操作分析》本文介绍了Pandas库的核心功能,包括处理结构化数据的Series和DataFrame数据结构,数据读取、清洗、分组聚合、合并、时间序列分析及大数据... 目录1. Pandas 概述2. 基本操作：数据读取与查看3. 索引操作：精准定位数据4. Group
阅读更多...
从基础到进阶详解Pandas时间数据处理指南

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据
阅读更多...
安装centos8设置基础软件仓库时出错的解决方案

安装centos8设置基础软件仓库时出错的解决方案

《安装centos8设置基础软件仓库时出错的解决方案》：本文主要介绍安装centos8设置基础软件仓库时出错的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录安装Centos8设置基础软件仓库时出错版本 8版本 8.2.200android4版本 javas
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2