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

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

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

AT最短路刷题2（本文难度rated 1000~ 1200）

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

文章目录

  • AT最短路刷题2（本文难度rated 1000~ 1200）
    • 1-**Souvenir**
    • 2-**Train**
    • 3-**バスと避けられない運命**
    • 4-**Crystal Switches**
    • 5-**Shortest Path Queries 2**
    • 6- Jumping Takahashi 2
    • 7-**Skiing**
    • 8-**Wizard in Maze**

1-Souvenir

https://atcoder.jp/contests/abc286/tasks/abc286_e

双关键字最短路。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18int dist[301][301];
int value[301][301];
int a[301];
char s[301][301];
int n;void dijkstra(int start){vector<bool> flag(n+1);for(int i=1;i<=n;i++){dist[start][i]=INF;}dist[start][start]=0;priority_queue<PII,vector<PII>,greater<PII>> q;q.push({0,start});value[start][start]=a[start];dist[start][start]=0;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;if(s[u][i]=='N')continue;if(dist[start][i]>dist[start][u]+1){dist[start][i] = dist[start][u]+1;value[start][i] = value[start][u] + a[i];q.push({dist[start][i],i});}else if(dist[start][i]==dist[start][u]+1 and value[start][i]<value[start][u]+a[i]){value[start][i] = value[start][u] + a[i];q.push({dist[start][i],i});}}}
}
void slove(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>s[i][j];for(int i=1;i<=n;i++){dijkstra(i);}int Q;cin>>Q;while(Q--){int u,v;cin>>u>>v;if(dist[u][v]==INF)cout<<"Impossible"<<endl;else cout<<dist[u][v]<<' '<<value[u][v]<<endl;}
}signed main(){slove();
}

2-Train

https://atcoder.jp/contests/abc192/tasks/abc192_e

最短路板子

/*对于每一条边：
火车发动的时间是： t = kx
所以可以开两个数组。数组1，记录 ai --> bi 城市的火车发车间隔，
数组2，记录 ai --> bi 代价如何写最短路？数组3记录 从起点到各点的最小值。
*/#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18const int N = 1e5+7;
struct node{int v;int w;int k;
};vector<vector<node>> g(N);
int dist[N];
bool flag[N];
int n,m;
void dijkstra(int x){for(int i=1;i<=n;i++)dist[i]=INF;dist[x]=0;priority_queue<PII,vector<PII>,greater<PII>> q;q.push({0,x});while(q.size()){int u = q.top().second;q.pop();if(flag[u])continue;flag[u]=1;for(auto i:g[u]){ //枚举能去的所有城市int v = i.v , w = i.w , k = i.k;int now = dist[u]; //当前时刻// 检查此时是不是刚好发车if(now%k==0){//如果刚好发车，那么直接加上边权if(dist[v]>dist[u]+w){dist[v] = dist[u]+w;q.push({dist[v],v});}}else{ //只能等下一班车int next = now / k + 1;now = k*next;if(dist[v]>now+w){dist[v]=now+w;q.push({dist[v],v});}}}}
}void slove(){cin>>n>>m;int x,y;cin>>x>>y;for(int i=1;i<=m;i++){int u,v,w,k;cin>>u>>v>>w>>k;g[u].push_back(node{v,w,k});g[v].push_back(node{u,w,k});}dijkstra(x);if(dist[y]==INF)cout<<-1<<endl;else cout<<dist[y]<<endl;}signed main(){slove();
}

3-バスと避けられない運命

https://atcoder.jp/contests/abc012/tasks/abc012_4

spfa板子

#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 = 305;
int dist[N][N];
void slove(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dist[i][j]=INF;}dist[i][i]=0;}for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;dist[u][v]=w;dist[v][u]=w;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);}}}int ans = INF;for(int i=1;i<=n;i++){int cnt=0;for(int j=1;j<=n;j++){if(dist[i][j]==INF)continue;cnt = max(cnt,dist[i][j]);}ans = min(cnt,ans);}cout<<ans<<endl;
}signed main(){slove();
}

4-Crystal Switches

https://atcoder.jp/contests/abc277/tasks/abc277_e

/*给你一张图：
如果边权是0，则代表开关关闭，不能通过
如果边权是1，代表开关打开，能通过对于每个结点，记录：1、结点编号
2、当前结点被反转
3、步数从起点开始bfs
遍历所有u能去的点，
如果边权是0：打开开关，加入状态： node = { v , 1 , step+1 }
如果边权是1：不管开关，加入状态： node = { v , 0 , step+1 }接下来对于v，如果图中所有边被反转：那么边权原来是1的，现在就是0所以还是要操作开关，node = { i , 0 , step+1 }
如果边权原来是0的，现在就是1所以不需要操作开关，node = { i , 1 , step+1 }*/#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18struct node{int u;int step;int opt;bool operator < (node b)const{return step>b.step;}
};struct gg{int v;int w; //边权
};const int N = 2e5+7;
vector<gg> g[N];//存图
vector<int> s(N); //哪些结点上面有开关
int n,m;int flag[N][2]; // 每个结点的每种状态只访问一次。
int dist[N]; //1到n的最短路void dijkstra(){for(int i=1;i<=n;i++)dist[i]=INF;dist[1]=0;priority_queue<node> q;node now;now.u = 1;now.opt=0;now.step=0;q.push(now);while(q.size()){int u = q.top().u;int step = q.top().step;int opt = q.top().opt;q.pop();if(flag[u][opt])continue;flag[u][opt]=1;if(u==n){cout<<step<<endl;return;}node nxt;for(auto i:g[u]){int v = i.v;int w = i.w;//第一种情况，当前图没被反转，且该边能通过if(opt==0 and w==1){nxt.step = step+w;nxt.u = v;nxt.opt = opt;q.push(nxt);}else if(opt==0 and w==0)//第二种情况，当前图没被反转，但该边不能通过{//检查这个点是否有开关if(s[u]==1){nxt.step = step +1;nxt.u = v;nxt.opt = 1;q.push(nxt);}// 如果此路不通，且u没有开关，那么爱莫能助}else if(opt==1 and w==1) //如果图被反转了一次，此时w=1 相当于不能通过{if(s[u]==1) //如果有开关，那么再反转一次全图{nxt.step = step+1;nxt.u = v;nxt.opt = 0;q.push(nxt);}}else if(opt==1 and w==0) //如果地图被反转1次，此时w=0，代表可以通过{nxt.step = step+1;nxt.u = v;nxt.opt = opt;q.push(nxt);}}}cout<<-1<<endl;}
void slove(){int k;cin>>n>>m>>k;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;g[u].push_back(gg{v,w});g[v].push_back(gg{u,w});}for(int i=1;i<=k;i++){int t;cin>>t;s[t]=1;}dijkstra();}signed main(){slove();
}

5-Shortest Path Queries 2

https://atcoder.jp/contests/abc208/tasks/abc208_d

纯板子，呆题

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18const int N = 405;
int dist[N][N];void slove(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dist[i][j]=INF;}dist[i][i]=0;}for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;dist[u][v]=w;}int ans = 0;for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);if(dist[i][j]!=INF){ans += dist[i][j];}}}}cout<<ans<<endl;
}signed main(){slove();
}

6- Jumping Takahashi 2

https://atcoder.jp/contests/abc257/tasks/abc257_d

二分+bfs

/*题目的意思是：让我们选择一个起始的蹦床。能从这个蹦床去到所有的蹦床的最小跳跃高度。然后找到这些最小跳跃高度中最小的那一个。我们可以二分跳跃高度 s然后枚举每一个起点。判断，这个跳跃高度是否能跳到任意一个蹦床。现在，问题就是，如何写check函数？可以写一个bfs，求连通性。如果最终连通，那么这个s是ok的时间复杂度： O(n^2 * log(1e10))*/#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18struct node{int id;int x;int y;int p;
};const int N =201;
node a[N];int ans = INF; //答案
int n;
bool flag[201];bool check(int mid,int start){memset(flag,0,sizeof flag);queue<node> q;q.push(a[start]);flag[start]=1;while(q.size()){int x = q.front().x;int y = q.front().y;int p = q.front().p;q.pop();node nxt;for(int i=1;i<=n;i++){if(flag[i])continue;int xx = a[i].x;int yy = a[i].y;int dist = abs(x-xx)+abs(y-yy);if(mid*p>=dist){q.push(a[i]);flag[i]=1;}}}for(int i=1;i<=n;i++){if(flag[i]==0)return false;}return true;
}
void work(int start){//二分跳跃高度int l=1, r = 1e10;while(l<r){int mid = l+r>>1;if(check(mid,start)){r=mid;}else{l=mid+1;}}ans = min(ans,l);
}
void slove(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y>>a[i].p;a[i].id=i;}for(int i=1;i<=n;i++){work(i);}cout<<ans<<endl;
}signed main(){slove();
}

7-Skiing

https://atcoder.jp/contests/abc237/tasks/abc237_e

最长路的处理方法之一：1、所有边权都乘上-1，然后跑spfa
值得注意的是，此题的时间需要不超过 O(NM)2、跑不了spfa，只能跑dijkstra
此时必须要从边权的计算方式，题目含义等条件入手。
来消除负权边。（吃经验 or 思维）

/*重力势能只与初始状态和末尾状态有关。初始状态是h[1],末尾状态是h[i]重力势能的变化就是 初状态 - 末状态 = h[1] - h[i]但是，这题没有这么简单。如果你走上坡路，那么消耗的是同等高度走下坡路的两倍。如果你走下坡路，只要你这个点是中间状态，那么一律不需要管，因为下坡路的贡献最终都会被抵消，剩下h[1]-[i]所以得到一个结论：假如初始状态和末尾状态都确定了，那么我们要想让最终答案最大。我们就必须使得走的上坡路的总代价越小 （这里说的是绝对值）也就是走最短路。而由于下坡路是没有影响的，所以下坡路的边权为0上坡路的边权 为1倍的  abs(h[u]-h[v])*/#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 = 2e5+7;struct node{int v;int w;
};vector<node> g[N];int n,m;
int h[N];
int dist[N];
bool flag[N];
priority_queue<PII,vector<PII>,greater<PII>> q;void dijkstra(){for(int i=1;i<=n;i++)dist[i]=INF;dist[1]=0;q.push({0,1});while(q.size()){int u = q.top().second;q.pop();for(auto i:g[u]){int w = i.w;int v = i.v;if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;q.push({dist[v],v});}}}
}
void slove(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>h[i];for(int i=1;i<=m;i++){int u,v;cin>>u>>v;int w = h[v]-h[u];if(w<0){ // u > vg[u].push_back(node{v,0});g[v].push_back(node{u,-w});}else // u<v{g[u].push_back(node{v,w});g[v].push_back(node{u,0});}}dijkstra();int ans = -INF;for(int i=1;i<=n;i++){ans = max(ans, h[1]-h[i] - dist[i]);}cout<<ans<<endl;}signed main(){slove();
}

8-Wizard in Maze

https://atcoder.jp/contests/abc176/tasks/abc176_d

bfs模板题

打的太多了，所以直接贴个答案上去。

#include<iostream>
#include<cstring>
#include<deque>
using namespace std;int h, w, ch, cw, dh, dw, dis[1005][1005];
//dis[i][j]表示从(ch, cw)出发到达(i, j)所消耗跳跃魔法次数的最小值
char a[1005][1005];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};struct node
{ //从(ch, cw)出发到达(x, y)所消耗跳跃魔法次数的最小值tint x, y, t;
};deque<node> q;void bfs()
{q.push_front(node{ch, cw, 0});dis[ch][cw] = 0;while(!q.empty()){int x = q.front().x, y = q.front().y, t = q.front().t;q.pop_front();//(x,y)普通移动能达到的子结点插入队首for(int i = 0; i <= 3; i++){int x_new = x + dx[i], y_new = y + dy[i];if(x_new < 1 || x_new > h || y_new < 1 || y_new > w) continue;if(a[x_new][y_new] == '#') continue;if(dis[x_new][y_new] <= dis[x][y]) continue;q.push_front(node{x_new, y_new, t});dis[x_new][y_new] = t;}//(x,y)跳跃魔法移动能达到的子结点插入队尾for(int x_new = x - 2; x_new <= x + 2; x_new++)for(int y_new = y - 2; y_new <= y + 2; y_new++){if(x_new < 1 || x_new > h || y_new < 1 || y_new > w) continue;if(a[x_new][y_new] == '#') continue;if(dis[x_new][y_new] <= dis[x][y] + 1) continue;q.push_back(node{x_new, y_new, t + 1});dis[x_new][y_new] = t + 1;}}
}int main()
{cin >> h >> w;cin >> ch >> cw;cin >> dh >> dw;for(int i = 1; i <= h; i++)for(int j = 1; j <= w; j++)cin >> a[i][j];memset(dis, 0x3f, sizeof(dis));bfs();if(dis[dh][dw] == 0x3f3f3f3f) cout << -1 << endl;else cout << dis[dh][dw] << endl;return 0;
}

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


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

相关文章

从基础到高级详解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