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。

相关文章

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型，3步搞定一个应
阅读更多...
MySQL中my.ini文件的基础配置和优化配置方式

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面：幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
poj 1511 Invitation Cards(spfa最短路)

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离，求来回到点1的最短路中的边权和。 因为边很大，不能用原来的dijkstra什么的，所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码： #include<stdio.h>#include<stack>using namespace std;const int M
阅读更多...
poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259： 题意：John的农场里n块地，m条路连接两块地，w个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来，看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码： #include<stdio.h>const int MaxN = 501;//农场数const int
阅读更多...
poj 1502 MPI Maelstrom（单源最短路dijkstra）

poj 1502 MPI Maelstrom（单源最短路dijkstra）

题目真是长得头疼，好多生词，给跪。 没啥好说的，英语大水逼。 借助字典尝试翻译了一下，水逼直译求不喷 Description： BIT他们的超级计算机最近交货了。（定语秀了一堆词汇那就省略吧再见） Valentine McKee的研究顾问Jack Swigert，要她来测试一下这个系统。 Valentine告诉Swigert：“因为阿波罗是一个分布式共享内存的机器，所以它的内存访问
阅读更多...
poj 3159 （spfa差分约束最短路） poj 1201

poj 3159 （spfa差分约束最短路） poj 1201

poj 3159: 题意： 每次给出b比a多不多于c个糖果，求n最多比1多多少个糖果。 解析： 差分约束。 这个博客讲差分约束讲的比较好： http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码： #include <iostream>#include <cstdio>#i
阅读更多...
hdu 3790 (单源最短路dijkstra）

hdu 3790 (单源最短路dijkstra）

题意： 每条边都有长度d 和花费p，给你起点s 终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。 解析： 考察对dijkstra的理解。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin
阅读更多...
poj 3255 次短路（第k短路） A* + spfa 或 dijkstra

poj 3255 次短路（第k短路） A* + spfa 或 dijkstra

题意： 给一张无向图，求从1到n的次短路。 解析： A* + spfa 或者 dijkstra。 详解见上一题：http://blog.csdn.net/u013508213/article/details/46400189 本题，spfa中，stack超时，queue的效率最高，priority_queue次之。 代码： #include <iostream>#i
阅读更多...
poj 2449 第k短路 A* + spfa

poj 2449 第k短路 A* + spfa

poj 2449： 题意： 给一张有向图，求第k短路。 解析： A* + spfa。 一下转自：http://blog.csdn.net/mbxc816/article/details/7197228 “描述一下怎样用启发式搜索来解决K短路。 首先我们知道A*的基础公式：f(x)=g(x)+h(x);对h(x)进行设计，根据定义h(x)为当前的x点到目标点t所需要的实际距
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2