1. Toy模板网首页
  2. > Toy博客

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

7月前 作者：louisdlee. 分类：Toy博客 阅读(37) 违法举报

这篇具有很好参考价值的文章主要介绍了0基础刷图论最短路 1（从ATcoder 0分到1800分）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

有个想法：
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模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • AtCoder Beginner Contest 310

    感觉F又双叒叕写复杂了 点杯咖啡，要 (p) 元，但可以用一个优惠券，使得咖啡只要 (q) 元，但你需要额外购买 (n) 个商品中（价格为 (a_i) ）的一个。 问点杯咖啡的最小价格。 考虑直接买还是使用优惠券，使用优惠券的话就选 (n) 个商品中价格最小的。 两种情况取最小

    2024年02月16日
    浏览(28)

  • AtCoder Beginner Contest 320

    给定 (a,b) ，输出 (a^b + b^a) 。 因为数不超过 (10) ，可以直接用 pow 计算然后转成 (int) 。不会有精度损失。 神奇的代码 给定一个字符串 (s) ，求长度最长的回文串。 因为长度只有 (100) ，可以直接枚举子串，然后暴力判断是不是回文串（翻转后是否和自身相同），复杂

    2024年02月08日
    浏览(38)

  • AtCoder Beginner Contest 348

    给定 (n) ，输出 (ooxooxoox...) ，长度为 (n) 。 按题意模拟即可。 神奇的代码 给定 (n) 个点，对每个点，求出与其距离最远的点的下标。 (n) 只有 (100) ，对于每个点，花 (O(n)) 遍历每个点最大化距离，时间复杂度为 (O(n^2)) 。 神奇的代码 (n) 个豌豆，每个豌豆有美味值

    2024年04月08日
    浏览(42)

  • AtCoder Beginner Contest 302

    给定怪物的血量 (a) 和你每次攻击扣除的血量 (b) ，问打多少次怪物才会死。 答案即为 (lceil frac{a}{b} rceil = lfloor frac{a + b - 1}{b} rfloor) 神奇的代码 给定一个二维网格，格子上有字母，找到一连串位置，使得其字符串为 (snuke) ，要求这一连串位置俩俩相邻，即有共边或

    2024年02月05日
    浏览(78)

  • AtCoder Beginner Contest 304

    依次给定每个人的姓名和年龄，排成一圈。从年龄最小的人依次输出姓名。 找到年龄最小的，依次输出就好了。 神奇的代码 给定一个数字，如果其超过三位数，则仅保留其最高三位，低位数字全部置为0。 读一个 string ，直接赋值即可。 神奇的代码 给定 (n) 个人的坐标，第

    2024年02月07日
    浏览(39)

  • AtCoder Beginner Contest 329

    劳累一天不该写题，启发式合并都写错了 给定一个字符串，将每个字符输出出来，中间留个空格。 遍历输出即可。 神奇的代码 给定一个数组，找出次大的数。 遍历一下，从非最大的数求一个最大值即可。 神奇的代码 给定一个字符串，问有多少个连续的子串，其由一个字母

    2024年02月05日
    浏览(75)

  • AtCoder Beginner Contest 339

    给一个网址，问它的后缀是多少。 找到最后的\\\'.\\\'的位置，然后输出后面的字符串即可。 python 可以一行。 神奇的代码 二维网格，上下左右相连，左上原点。初始全部为白色，位于原点，面朝上。 进行 (n) 次操作，每次操作，将当前格子颜色黑白反转，然后 如果原来是白色

    2024年02月19日
    浏览(31)

  • AtCoder Beginner Contest 340

    给定等差数列的 首项 、 末项 、 公差 。 输出这个等差数列。 从 首相 依次累加 公差 到 末项 即可。 神奇的代码 依次进行 (Q) 次操作，分两种。 1 x ，将 x 放到数组 (a) 的末尾。 2 k ，输出数组 (a) 的倒数第 (k) 项。 用 vector 模拟即可，操作 2 可快速寻址访问。 神奇的代

    2024年02月19日
    浏览(33)

  • AtCoder Beginner Contest 314

    怎么好多陌生单词 审核怎么这么逆天，半小时还没审完 给定 (pi) 的值以及数 (n) ，要求保留 (n) 位小数输出，不四舍五入。 字符串形式储存然后截取末尾即可。 神奇的代码 (n) 个人玩轮盘赌游戏，简单说就是一个转盘有 (37) 个数字以及一个箭头，箭头会等概率停在某

    2024年02月13日
    浏览(40)

  • AtCoder Beginner Contest 308

    这几天在收拾东西搬家，先附上代码，晚点补上题解 补完了 感觉这次FG都写不太明白 给定八个数，问是否满足以下要求： 不严格升序 每个数在 (100 sim 675) 之间 每个数都是 (25) 的倍数 依次对每个数判断是否符合这三个条件即可。 神奇的代码 高桥吃 (n) 份寿司，寿司分

    2024年02月11日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包