제출 #1102639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102639		12345678	Robot (JOI21_ho_t4)	C++17	0 / 100	3070 ms	59492 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, mn=1e18, cnt;
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], dp[nx][2];

ll getval(ll idx, ll c, ll t)
{
    if (dp[idx][t].find(c)==dp[idx][t].end()) return 1e18;
    return dp[idx][t][c];
}

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]++;
    dp[1][0][-1]=0;
    pq.push({0, 1, -1, 0});
    while (!pq.empty())
    {
        auto [cst, u, p, t]=pq.top();
        pq.pop();
        //cout<<"debug "<<cst<<' '<<u<<' '<<p<<' '<<t<<'\n';
        for (auto [v, c]:d[u])
        {
            if (mp[u][c]>2||((mp[u][c]==2)&&p!=c))
            {
                if (cst+1<getval(v, c, 1)) dp[v][1][c]=cst+1, pq.push({cst+1, v, c, 1});
            }
            else if (mp[u][c]==2&&p==c)
            {
                if (t==1)
                {
                    if (cst<getval(v, c, 0)) dp[v][0][c]=cst, pq.push({cst, v, c, 0});
                }
                else
                {
                    if (cst+1<getval(v, c, 1)) dp[v][1][c]=cst+1, pq.push({cst+1, v, c, 1});
                }
            }
            else
            {
                if (cst<getval(v, c, 0)) dp[v][0][c]=cst, pq.push({cst, v, c, 0});
            }
        }
    }
    for (auto x:dp[n][0]) mn=min(mn, x.second);
    for (auto x:dp[n][1]) mn=min(mn, x.second);
    if (mn==1e18) cout<<-1;
    else cout<<mn;
}

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