当前位置：网站首页>2022ACM夏季集训周报（四）

2022ACM夏季集训周报（四）

2022-07-27 12:52:00 【Eloi0424】

22.07.26 Monday

"蔚来杯"2022牛客暑期多校训练营3

J Journey

最短路 01BFS
题意： n 个十字入口右转必为绿灯其他转向都为红灯
问你从道路 s1->s2 到 t1->t2 的最少红灯数
思路：其实就是把道路当作节点跑01BFS就行
注意这里建图很麻烦，可以给道路标序号。
对每个十字路口开一个map来确定对应道路的标号

代码：

// #pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
#include <bitset>
#include <queue>
#include <cstdio>
#include <map>
#include <algorithm>
#include <stack>
// #include <random>
using namespace std;
#define int128 __int128_t
typedef long long ll;
// #define ll int
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
struct triplet
{
    
    ll first, second, third;
};
const ll INF = 1e9;
const ll MAXN = 2e6 + 5;
const ll MOD = 998244353;
const ll Base = 131;
// mt19937_64 mrand(random_device{}());
int n;
int c[5];
map<int,int> num[MAXN];
vector <P> MAP[MAXN];
int dis[MAXN];
bool vis[MAXN];
int s,t;
void BFS()
{
    
    deque <int> q;
    q.push_back(s);
    dis[s]=0;
    while(!q.empty())
    {
    
        int from=q.front();
        q.pop_front();
        if(vis[from])
            continue;
        vis[from]=1;
        for(auto i:MAP[from])
        {
    
            int to=i.first,w=i.second;
            if(dis[to]>dis[from]+w)
                dis[to]=dis[from]+w;
            if(w)
                q.push_back(to);
            else
                q.push_front(to);
        }
    }

}
void solve()
{
    
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
    
        for(int j=1;j<=4;j++)
            cin>>c[j];
        for(int j=1;j<=4;j++)
        {
    
            if(c[j]==0)
                continue;
            if(!num[c[j]].count(i))
            {
    
                cnt++;
                num[c[j]][i]=cnt;
            }
            if(!num[i].count(c[j%4+1]))
            {
    
                cnt++;
                num[i][c[j%4+1]]=cnt;
            }
            MAP[num[c[j]][i]].push_back(P(num[i][c[j%4+1]],0));
            for(int k=1;k<=4;k++)
            {
    
                if(k!=j%4+1)
                {
    
                    if(!num[i].count(c[k]))
                    {
    
                        cnt++;
                        num[i][c[k]]=cnt;
                    }
                    MAP[num[c[j]][i]].push_back(P(num[i][c[k]],1));
                }
            }
        }
    }
    int s1,s2,t1,t2;
    cin>>s1>>s2>>t1>>t2;
    s=num[s1][s2];
    t=num[t1][t2];



    for(int i=1;i<=cnt;i++)
        dis[i]=1e9;
    BFS();
    if(dis[t]==1e9)
        cout<<-1;
    else
        cout<<dis[t];
}
int main()
{
    
    // freopen("Test_File\\Test.in", "r", stdin);
    // freopen("Test_File\\My_code.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    // int T;
    // cin >> T;
    // while (T--)
    solve();
    return 0;
}

// Code By Eloi