广州网站搜索排名,各大网站域名,怀化优化办,白银市网站建设AT最短路刷题3#xff08;本文难度rated 1200~ 1400#xff09;
题目来源#xff1a;Atcoder 题目收集#xff1a; https://atcoder-tags.herokuapp.com/tags/Graph/Shortest-Path #xff08;里面按tag分类好了Atcoder的所有题目#xff0c;类似cf#xff09; #x…AT最短路刷题3本文难度rated 1200~ 1400
题目来源Atcoder 题目收集 https://atcoder-tags.herokuapp.com/tags/Graph/Shortest-Path 里面按tag分类好了Atcoder的所有题目类似cf 访问需要魔法
这算是一个题单各位有兴趣可以按照这个顺序来刷。 我的代码仅供参考。 会提示关键性质和步骤。 部分有注释。 洛谷、知乎、可以搜到题解。 文章目录 AT最短路刷题3本文难度rated 1200~ 14001-**身体バランス**2-**Road Reduction****3 - Swap Places**4-**Come Back Quickly**5-**正直者の高橋くん**6-**joisinos travel**7-**Traveler**8- **Merge Set** 1-身体バランス
这道题其实就是求两边dijkstra
一遍正图
一遍反图然后枚举每个点
1 -- i 的路径长度 i-- n 的路径长度
并且 dist1[i]dist2[i] dist1[n]然后找有没有这样的点就行了。贴答案ing#include bits/stdc.h#define rep(i,n) for(int i0;i(n);i)using namespace std;templateclass T struct edge{int to;T wt;edge(int to,const T wt):to(to),wt(wt){}
};
templateclass T using weighted_graphvectorvectoredgeT;templateclass T
vectorT Dijkstra(const weighted_graphT G,int s){const T INFnumeric_limitsT::max();int nG.size();vectorT d(n,INF); d[s]0;priority_queuepairT,int Q; Q.emplace(0,s);while(!Q.empty()){T d0-Q.top().first;int uQ.top().second; Q.pop();if(d0d[u]) continue;for(const auto e:G[u]){int ve.to;if(d[v]d[u]e.wt) d[v]d[u]e.wt, Q.emplace(-d[v],v);}}return d;
}const int INF129;int main(){int n,m,s,t; scanf(%d%d%d%d,n,m,s,t); s--; t--;weighted_graphint G(n);rep(i,m){int u,v,c; scanf(%d%d%d,u,v,c); u--; v--;G[u].emplace_back(v,c);G[v].emplace_back(u,c);}auto d1Dijkstra(G,s);auto d2Dijkstra(G,t);rep(u,n) if(d1[u]INF d1[u]d2[u]) return printf(%d\n,u1),0;puts(-1);return 0;
}
2-Road Reduction 最短路 https://atcoder.jp/contests/abc252/tasks/abc252_e
一张图有N个点。
M条边。
现在我们要删除一些边最终会剩下N-1条边。然后求出
1到每个城市的最短路径这个问题只是看上去很唬人。我们只要知道一个事情
如果一张图是连通的那么它的边最少都要是N-1由于最短路只会比这个多不会比这个少。
所以直接跑最短路。
拓展到谁就是谁。#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define PII pairint,pairint,int
#define INF 1e18
const int N 2e57;
struct node{int v;int w;int id; //edge编号
};
struct edge{int u;int id;int step;bool operator(edge b)const{return stepb.step;}
};
vectornode g[N];
int dist[N];
int flag[N];
int n,m;void dijkstra(){for(int i1;in;i)dist[i]INF;dist[1]0;priority_queueedge q;q.push(edge{1,-1,0});while(q.size()){int u q.top().u;int id q.top().id;q.pop();if(flag[u])continue;flag[u]1;if(id!-1){cout id ;}for(auto i:g[u]){int v i.v;int w i.w;int id i.id;if(dist[v]dist[u]w){dist[v]dist[u]w;q.push(edge{v,id,dist[v]});}}}
}
void slove(){cinnm;for(int i1;im;i){int u,v,w;cinuvw;g[u].push_back(node{v,w,i});g[v].push_back(node{u,w,i});}dijkstra();
}signed main(){slove();
}3 - Swap Places
https://atcoder.jp/contests/abc289/tasks/abc289_e] BFS 存两个点状态 /*
一种新类型
想过双搜但其实这比双搜简单。
因为他有限制条件。1、它们两个移动到的顶点必须是不同颜色
2、它们两个要同时到达起点和终点然后我们再思考一下flag这么写
是一个点不能重复还是一个状态不能重复。
显然是一个状态也就是两个人所在的位置不能重复入队我们bfs可不可以回头或者一个人停下来等为什么要回头假如一方更快到达一方更慢到达。需要有人停下来等下。显然这种情况是不会发生的...因为它们两个是同时移动而不是先后移动。所以只要存在路径它们能一直往前走那么就可以同时到达。所以我们的flag函数记录的是一个状态不可到达两次*/#include bits/stdc.h
using namespace std;
#define ll long long
#define PII pairint,int
#define endl \n
#define INF 1e18
#define int long long
const int N 2001; // 1e6 5struct node{int n1;int n2;int step;
};
int color[N];
bool flag[N][N];void solve() {memset(color,0,sizeof color);memset(flag,0,sizeof flag);vectorint g[N];int n,m;cinnm;for(int i1;in;i)cincolor[i];for(int i1;im;i){int u,v;cinuv;g[u].push_back(v);g[v].push_back(u);}queuenode q;q.push(node{1,n,0});while(q.size()){int n1 q.front().n1;int n2 q.front().n2;int step q.front().step;q.pop();if(flag[n1][n2])continue;flag[n1][n2]1;if(n1n and n21){coutstependl;return;}for(auto i:g[n1]){for(auto j:g[n2]){if(color[i]!color[j])q.push({i,j,step1});}}}cout-1endl;}
signed main () {std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin t;while(t --)solve();
}4-Come Back Quickly
https://atcoder.jp/contests/abc191/tasks/abc191_e dijkstra /*
对于每个城镇我们需要找到一个城镇1、从起点出发走到那里还能再回来
2、出发回来的时间最短N2000
跑2000遍最短路。对于每个起点 更新 dist[i][j]
跑完之后
对于每个起点找到一个点使得 dist[i][j]dist[j][i] 最短
如果ij 那么只加一遍。关于输入
对于同一对点只取最短的路。
一开始全部初始为INF*/#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define PII pairint,int
#define INF 1e18
const int N 2001;
int n,m;
struct node{int v;int w;
};
vectornode g[N];
int dist[N];
bool flag[N];
int d[N][N];void dijkstra(int start){for(int i1;in;i) dist[i]INF;for(int i1;in;i) flag[i]0;dist[start]0;priority_queuePII,vectorPII,greaterPII q;q.push({0,start});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;int w i.w;if(dist[v]dist[u]w){dist[v]dist[u]w;d[start][v] min(d[start][v],dist[v]);q.push({dist[v],v});}}}}
void slove(){cinnm;for(int i1;in;i)for(int j1;jn;j)d[i][j]INF;for(int i1;im;i){int u,v,w;cinuvw;d[u][v]min(d[u][v],w);}for(int i1;in;i){for(int j1;jn;j){if(i!j){if(d[i][j]!INF)g[i].push_back(node{j,d[i][j]});}}}for(int i1;in;i){dijkstra(i);}for(int i1;in;i){int ans INF;for(int j1;jn;j){if(ij){ans min(ans,d[i][j]);}else{ans min(ans,d[i][j]d[j][i]);}}if(ansINF)cout-1endl;else coutansendl;}}signed main(){slove();
}5-正直者の高橋くん
https://atcoder.jp/contests/abc021/tasks/abc021_c dpdijkstra /*
新的题型求起点到终点的最短路有多少条。考虑dp设dp[i][j]表示从起点出发走到i且距离为j的路的数量假设结尾是end
答案是 dp[end][dist];那么从所有能扩展到end的点中
dp[end][dist] dp[i][dist-1]我们考虑初始是怎么得到状态的从起点开始扩展dp[v][j] dp[u][j-1]初始化就是
dp[start][0]1;
*/
#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define PII pairint,int
#define INF 1e18
const int mod 1e97;
const int N 101;
int dp[101][1000]; //答案
int dist[101]; //最短路
bool flag[101];
vectorint g[N];int a,b; //起点终点
int n,m;void dijkstra(){for(int i1;in;i)dist[i]INF;dist[a]0;dp[a][0]1;priority_queuePII,vectorPII,greaterPII q;q.push({0,a});while(q.size()){int u q.top().second;q.pop();if(flag[u])continue;flag[u]1;for(auto i:g[u]){if(dist[i]dist[u]1){dist[i]dist[u]1;dp[i][dist[i]]( dp[i][dist[i]]dp[u][dist[u]])%mod;q.push({dist[i],i});}}}coutdp[b][dist[b]]%modendl;
}
void slove(){cinn;cinab;cinm;for(int i1;im;i){int u,v;cinuv;g[u].push_back(v);g[v].push_back(u);}dijkstra();}signed main(){slove();
}6-joisino’s travel
https://atcoder.jp/contests/abc073/tasks/abc073_d floyd 全排列 #includeiostream
#includecstring
#includealgorithm
using namespace std;int n,m,R,dist[300][300],r[10];int main()
{memset(dist,0x3f,sizeof dist);int Min,ans;cinnmR;for(int i0;iR;i)cinr[i];for(int i0;im;i){int x,y,z;cinxyz;dist[x][y]dist[y][x]z;}for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j)if(dist[i][k]dist[k][j]dist[i][j])dist[i][j]dist[i][k]dist[k][j];sort(r,rR);ans0x3f3f3f3f;do{Min0;for(int i0;iR-1;i)Mindist[r[i]][r[i1]];ansmin(Min,ans);}while(next_permutation(r,rR));coutans;
}7-Traveler
https://atcoder.jp/contests/abc197/tasks/abc197_e
/*
这是一个新问题
如果你必须要走完所有点 or 必须走完所选中的点。
你的最短路是多少建图如果小球ID一样那么两者之间建立双向边。标记数组
标记每个球其实最终这是一条链。
因为对于id不一样的小球我们是线性升序的也就是一条链but... 对于ID一样的小球我们必须采用特定的顺序。使之变成一条链。对于id一样的小球我们只关心分布两端的球。
中间的球在拣两端的球的路上会被捡走。而对于同一种id的小球我们最后拣左端 还是 拣右段 是不知道的 。这需要跟下一种要捡的id有关。
而。。下一种要捡的id也是找左端和右段。显然状态有点太多了。
所以考虑dp设dp[i][2]表示当前是 id i的小球我们最后一次是捡 0左边/1右边 的最短路假设序列已经排好序捡左边 abs(now - d[1]) abs(d[k] - d[1])
显然我们还需要一个中间变量记录每一种id开始捡的时候的坐标。捡右边abs(now - d[k]) abs(d[1]-d[k]) ;*/#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define PII pairint,int
#define INF 1e18
const int N 2e57;
int dp[N][2];
setint color;
vectorint g[N];
void slove(){int n;cinn;for(int i1;in;i){int x,c;cinxc;color.insert(c);g[c].push_back(x);}for(auto i:color){sort(g[i].begin(),g[i].end());}int now 0;for(auto i color.begin() ; i!color.end();i){int id *i;auto it i;auto is it;if(it!color.begin()){is--;int pre *is; //上一次的小球id//当前id的小球最后一次收集是左边// 上一次的小球收集最后是在左边int temp1 dp[pre][0] abs(g[pre][0]-g[id][g[id].size()-1]) abs(g[id][0]-g[id][g[id].size()-1]);//上一次的小球收集在右边int temp2 dp[pre][1] abs(g[pre][g[pre].size()-1]-g[id][g[id].size()-1]) abs(g[id][0]-g[id][g[id].size()-1]);dp[id][0] min(temp1,temp2);//当前id的小球最后一次收集在右边// 上一次的小球收集最后是在左边temp1 dp[pre][0] abs(g[pre][0]-g[id][0]) abs(g[id][0]-g[id][g[id].size()-1]);//上一次的小球收集在右边temp2 dp[pre][1] abs(g[pre][g[pre].size()-1]-g[id][0]) abs(g[id][0]-g[id][g[id].size()-1]);dp[id][1] min(temp1,temp2);}else{//当前id的小球最后一次收集是左边// 上一次的在起点int temp1 0 abs(0-g[id][g[id].size()-1]) abs(g[id][0]-g[id][g[id].size()-1]);//上一次的在起点int temp2 0 abs(0-g[id][g[id].size()-1]) abs(g[id][0]-g[id][g[id].size()-1]);dp[id][0] min(temp1,temp2);//当前id的小球最后一次收集在右边// 上一次的在起点temp1 0 abs(0-g[id][0]) abs(g[id][0]-g[id][g[id].size()-1]);//上一次的在起点temp2 0 abs(0-g[id][0]) abs(g[id][0]-g[id][g[id].size()-1]);dp[id][1] min(temp1,temp2);}}// 加上回到起点的距离coutmin(dp[*color.rbegin()][1]abs(g[*color.rbegin()][g[*color.rbegin()].size()-1]),dp[*color.rbegin()][0] abs(g[*color.rbegin()][0]) )endl;}signed main(){slove();
}8- Merge Set
https://atcoder.jp/contests/abc302/tasks/abc302_f
警钟长鸣N要开大点
/*
一共有N个集合
每个集合包含图内的一些点。当前仅当两个集合内有交点那么我们可以将这两个集合合并集合内部是互通的。我们现在要从1到M请问需要连接多少集合。我们可以在每个集合内部连接一条边权为0的点。在每个集合间连接一条边权为1的点。然后跑一遍最短路。问题是
如何在集合之间连边?考虑集合之间是如何互通的这题算是一个套路的建图题。对于这种集合间连边的问题
我们可以给每个集合都编号。这个编号不能和现在有的点重复。
所以可以考虑iM然后把每个集合内部的点都和这个集合相连。点到集合的边为0
集合到点的边为1答案就是最短路-1
*/#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define PII pairint,int
#define INF 1e18struct node{int v;int w;
};
struct point{int u;int step;bool operator (point b)const{return stepb.step;}
};const int N 5e66;
int dist[N];
int flag[N];
vectornode g[N];
void slove(){int n,m;cinnm;for(int i1;in;i){int len;cinlen;while(len--){int v;int u im;cinv;g[v].push_back(node{u,1});g[u].push_back(node{v,1});}}priority_queuepoint q;q.push(point{1,0});while(q.size()){int u q.top().u;int step q.top().step;q.pop();if(flag[u])continue;flag[u]1;if(um){coutstep/2-1endl;return;}for(auto i : g[u]){int v i.v;int w i.w;q.push(point{v,wstep});}}cout-1endl;}signed main(){slove();
}
