ATC最短路1 (本文难度rated 0~ 1000)
题目来源:Atcoder
题目收集:
https://atcoder-tags.herokuapp.com/tags/Graph/Shortest-Path
(里面按tag分类好了Atcoder的所有题目,类似cf)
(访问需要魔法)
这算是一个题单,各位有兴趣可以按照这个顺序来刷。
我的代码仅供参考。
会提示关键性质和步骤。 部分有注释。
洛谷、知乎、可以搜到题解。
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 1e18
void 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 1e18
void 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算完了话,再重新清空标记,去计算2
N<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-1
N的取值范围是 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 1e18
int 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 1e18
int 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 1e18
int 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];
//floyed
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]);
}
}
}
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文章来源:https://www.toymoban.com/news/detail-852715.html
一点小思考:文章来源地址https://www.toymoban.com/news/detail-852715.html
有个想法:
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 1e18
int 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分)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!