首页 > 其他分享 >Sky Inc, Programming Contest 2023(AtCoder Beginner Contest 289)E

Sky Inc, Programming Contest 2023(AtCoder Beginner Contest 289)E

时间:2023-02-14 20:23:52浏览次数:64  
标签:AtCoder Beginner Contest int nx ny 2010 dp

E - Swap Places

题链
考虑dp[i][j]表示第一个点到达i点 第二个点到达j点的min
然后bfs即可 时间复杂度为状态数

int dp[2010][2010],n,m,c[2010];//dp[i][j]表示到达(i,j)的min
vector<int>g[2010];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>c[i];
        g[i].clear();
    }
    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=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j]=INF;
        }
    }
    queue<PII>q;
    dp[1][n]=0;
    q.push({1,n});
    while(q.size()){
        auto [x,y]=q.front();q.pop();
        for(auto nx:g[x]){
            for(auto ny:g[y]){
                if(dp[nx][ny]>dp[x][y]+1&&c[nx]!=c[ny]){
                    dp[nx][ny]=min(dp[nx][ny],dp[x][y]+(c[nx]!=c[ny]));
                    q.push({nx,ny});
                }
            }
        }
    }
    if(dp[n][1]==INF)cout<<-1<<endl;
    else cout<<dp[n][1]<<endl;
}

标签:AtCoder,Beginner,Contest,int,nx,ny,2010,dp
From: https://www.cnblogs.com/ycllz/p/17120778.html

相关文章

  • AtCoder随做
    突然发现只有我没写过AT。没写题解不意味着没做,有的忘了写或者太草率了就算了。部分前言删了。ABC020D题解\[\sum_{i=1}^n\operatorname{lcm}\{i,k\}\\=k\sum_{i=......
  • AtCoder Beginner Contest 289
    A-flip(abc289a)题目大意给定一个\(01\)字符串,翻转\(01\)输出解题思路模拟即可神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlo......
  • AtCoder Beginner Contest 289
    A.flipC++Code#include<bits/stdc++.h>usingi64=longlong;intmain(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::str......
  • Atcoder Beginner Contest 289
    ContestResult做出了\(\texttt{A}\sim\texttt{F}\),\(\texttt{G}\)题有点思路,但时间不够了。\(\texttt{E}\)题状态设计太慢,复杂度其实也没算明白,\(\texttt{F}\)题......
  • AtCoder Beginner Contest 288
    E.WishList假设你需要选择\(B_1,B_2,..,B_k\)这\(K\)个元素编号。假设当前你选择\(B_i\)元素,且前面\(i-1\)个元素\(B_1,B_2,...,B_{i-1}\)选择了\(x\)个(\(......
  • USACO 2017 January Contest, Silver Problem 1. Cow Dance Show 二分+优先队列 普及
    USACO2017JanuaryContest,SilverProblem1.CowDanceShow二分+优先队列+贪心题目链接:http://www.usaco.org/index.php?page=viewproblem2&cpid=690P3611[USACO......
  • 2019-2020 ICPC, Asia Jakarta Regional Contest E - Songwriter 差分约束(随机化优
    最短路三角形不等式:Xi<=Xj+w(根据最短路的定义,要是不满足的话就不是最短路了)给出若干个形如Xi-Xj<=w的约束条件,考虑求一组合法的解。把问题转化成求最短路,对于Xi-Xj<=w,我......
  • USACO 2023 January Contest, Platinum 题解
    TractorPaths题意:给定\(n\)个不交区间,两个区间之间有边当且仅当这两个区间的交非空。\(Q\)次询问,每次给定\(u,v\),求从\(u\)到\(v\)的最短路和最短路可能经过的点......
  • VII MaratonUSP Freshman Contest
    A.AbductingNathan!每得2k分会轮回,模2k后,小于k先手,反之后手#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intread(){ intx=0,ch=g......
  • AtCoder Beginner Contest 288
    《D-RangeAddQuery》题目大意:给定一个长度为n的序列s,和一个整数k我们可以对s进行无数次如下操作:1、选定s中的一个下标i(1<=i<=n-k+1)2.......