제출 #1102621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102621		12345678	Robot (JOI21_ho_t4)	C++17	0 / 100	3170 ms	2077212 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

ll n, m, u, v, c, p, dp[nx][2];
priority_queue<tuple<ll, ll, ll, ll>, vector<tuple<ll, ll, ll, ll>>, greater<tuple<ll, ll, ll, ll>>> pq;
vector<pair<ll, ll>> d[nx];
map<ll, ll> mp[nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>u>>v>>c>>p, d[u].push_back({v, c}), d[v].push_back({u, c}), mp[u][c]++, mp[v][c]++;
    for (int i=1; i<=n; i++) dp[i][0]=dp[i][1]=1e18;
    dp[1][0]=0;
    pq.push({0, 1, -1, 0});
    while (!pq.empty())
    {
        auto [cst, u, p, t]=pq.top();
        pq.pop();
        for (auto [v, c]:d[u])
        {
            if (mp[u][c]>2||((mp[u][c]==2)&&p!=c))
            {
                if (cst+1<=dp[v][1]) dp[v][1]=cst+1, pq.push({cst+1, v, c, 1});
            }
            else if (mp[u][c]==2&&p==c)
            {
                if (t==1)
                {
                    if (cst<=dp[v][0]) dp[v][0]=cst, pq.push({cst, v, c, 0});
                }
                else
                {
                    if (cst+1<=dp[v][1]) dp[v][1]=cst+1, pq.push({cst+1, v, c, 1});
                }
            }
            else
            {
                if (cst<=dp[v][0]) dp[v][0]=cst, pq.push({cst, v, c, 0});
            }
        }
    }
    if (min(dp[n][0], dp[n][1])==1e18) cout<<-1;
    else cout<<min(dp[n][0], dp[n][1]);
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42