Submission #1103521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103521		12345678	Robot (JOI21_ho_t4)	C++17	100 / 100	531 ms	49584 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

struct node
{
    ll mn, sm;
    vector<pair<ll, ll>> d;
    node(): mn(1e18), sm(0){}
};

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

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

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