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。

相关文章

零基础学习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所需要的实际距
阅读更多...
【Linux 从基础到进阶】Ansible自动化运维工具使用

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具，采用无代理架构（agentless），基于 SSH 连接进行管理，具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用，旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2