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

AT最短路刷题3（本文难度rated 1200~ 1400）

题目来源：Atcoder
题目收集：
https://atcoder-tags.herokuapp.com/tags/Graph/Shortest-Path
（里面按tag分类好了Atcoder的所有题目，类似cf）
（访问需要魔法）

这算是一个题单，各位有兴趣可以按照这个顺序来刷。
我的代码仅供参考。
会提示关键性质和步骤。 部分有注释。
洛谷、知乎、可以搜到题解。

1-身体バランス

这道题其实就是求两边dijkstra
一遍正图
一遍反图然后枚举每个点，
1 --> i  的路径长度  == i--> n 的路径长度
并且， dist1[i]+dist2[i] == dist1[n]然后找有没有这样的点就行了。贴答案ing

#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(n);i++)using namespace std;template<class T> struct edge{int to;T wt;edge(int to,const T& wt):to(to),wt(wt){}
};
template<class T> using weighted_graph=vector<vector<edge<T>>>;template<class T>
vector<T> Dijkstra(const weighted_graph<T>& G,int s){const T INF=numeric_limits<T>::max();int n=G.size();vector<T> d(n,INF); d[s]=0;priority_queue<pair<T,int>> Q; Q.emplace(0,s);while(!Q.empty()){T d0=-Q.top().first;int u=Q.top().second; Q.pop();if(d0>d[u]) continue;for(const auto& e:G[u]){int v=e.to;if(d[v]>d[u]+e.wt) d[v]=d[u]+e.wt, Q.emplace(-d[v],v);}}return d;
}const int INF=1<<29;int main(){int n,m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); s--; t--;weighted_graph<int> 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 d1=Dijkstra(G,s);auto d2=Dijkstra(G,t);rep(u,n) if(d1[u]<INF && d1[u]==d2[u]) return printf("%d\n",u+1),0;puts("-1");return 0;
}

2-Road Reduction

最短路

https://atcoder.jp/contests/abc252/tasks/abc252_e

一张图，有N个点。
M条边。
现在我们要删除一些边，最终会剩下N-1条边。然后，求出：
1到每个城市的最短路径这个问题只是看上去很唬人。我们只要知道一个事情：
如果一张图是连通的，那么它的边最少都要是N-1由于，最短路只会比这个多，不会比这个少。
所以，直接跑最短路。
拓展到谁就是谁。#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,pair<int,int>>
#define INF 1e18
const int N = 2e5+7;
struct node{int v;int w;int id; //edge编号
};
struct edge{int u;int id;int step;bool operator<(edge b)const{return step>b.step;}
};
vector<node> g[N];
int dist[N];
int flag[N];
int n,m;void dijkstra(){for(int i=1;i<=n;i++)dist[i]=INF;dist[1]=0;priority_queue<edge> 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(){cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;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 pair<int,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);vector<int> g[N];int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>color[i];for(int i=1;i<=m;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}queue<node> 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(n1==n and n2==1){cout<<step<<endl;return;}for(auto i:g[n1]){for(auto j:g[n2]){if(color[i]!=color[j])q.push({i,j,step+1});}}}cout<<-1<<endl;}
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、出发+回来的时间最短N=2000
跑2000遍最短路。对于每个起点  ，更新 dist[i][j]
跑完之后，
对于每个起点，找到一个点使得  dist[i][j]+dist[j][i] 最短
如果i==j 那么只加一遍。关于输入：
对于同一对点，只取最短的路。
一开始全部初始为INF*/#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 =2001;
int n,m;
struct node{int v;int w;
};
vector<node> g[N];
int dist[N];
bool flag[N];
int d[N][N];void dijkstra(int start){for(int i=1;i<=n;i++) dist[i]=INF;for(int i=1;i<=n;i++) flag[i]=0;dist[start]=0;priority_queue<PII,vector<PII>,greater<PII>> 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(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=INF;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;d[u][v]=min(d[u][v],w);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j){if(d[i][j]!=INF)g[i].push_back(node{j,d[i][j]});}}}for(int i=1;i<=n;i++){dijkstra(i);}for(int i=1;i<=n;i++){int ans = INF;for(int j=1;j<=n;j++){if(i==j){ans = min(ans,d[i][j]);}else{ans = min(ans,d[i][j]+d[j][i]);}}if(ans==INF)cout<<-1<<endl;else cout<<ans<<endl;}}signed main(){slove();
}

5-正直者の高橋くん

https://atcoder.jp/contests/abc021/tasks/abc021_c

dp+dijkstra

/*
新的题型：求起点到终点，的最短路有多少条。考虑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;
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18
const int mod = 1e9+7;
const int N = 101;
int dp[101][1000]; //答案
int dist[101]; //最短路
bool flag[101];
vector<int> g[N];int a,b; //起点终点
int n,m;void dijkstra(){for(int i=1;i<=n;i++)dist[i]=INF;dist[a]=0;dp[a][0]=1;priority_queue<PII,vector<PII>,greater<PII>> 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});}}}cout<<dp[b][dist[b]]%mod<<endl;
}
void slove(){cin>>n;cin>>a>>b;cin>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;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 + 全排列

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;int n,m,R,dist[300][300],r[10];int main()
{memset(dist,0x3f,sizeof dist);int Min,ans;cin>>n>>m>>R;for(int i=0;i<R;i++)cin>>r[i];for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;dist[x][y]=dist[y][x]=z;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(dist[i][k]+dist[k][j]<dist[i][j])dist[i][j]=dist[i][k]+dist[k][j];sort(r,r+R);ans=0x3f3f3f3f;do{Min=0;for(int i=0;i<R-1;i++)Min+=dist[r[i]][r[i+1]];ans=min(Min,ans);}while(next_permutation(r,r+R));cout<<ans;
}

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]) ;*/#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;
int dp[N][2];
set<int> color;
vector<int> g[N];
void slove(){int n;cin>>n;for(int i=1;i<=n;i++){int x,c;cin>>x>>c;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);}}// 加上回到起点的距离cout<<min(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的点。然后跑一遍最短路。问题是：
如何在集合之间连边?考虑集合之间是如何互通的？这题算是一个套路的建图题。对于这种集合间连边的问题：
我们可以给每个集合都编号。这个编号不能和现在有的点重复。
所以可以考虑i+M然后把每个集合内部的点，都和这个集合相连。点到集合的边为0
集合到点的边为1答案就是最短路-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 v;int w;
};
struct point{int u;int step;bool operator <(point b)const{return step>b.step;}
};const int N = 5e6+6;
int dist[N];
int flag[N];
vector<node> g[N];
void slove(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int len;cin>>len;while(len--){int v;int u = i+m;cin>>v;g[v].push_back(node{u,1});g[u].push_back(node{v,1});}}priority_queue<point> 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(u==m){cout<<step/2-1<<endl;return;}for(auto i : g[u]){int v = i.v;int w = i.w;q.push(point{v,w+step});}}cout<<-1<<endl;}signed main(){slove();
}