제출 #1286157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286157		Faisal_Saqib	Robot (JOI21_ho_t4)	C++20	0 / 100	3096 ms	72020 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const int N=2e5+100;
int a[N],b[N],c[N],p[N];
vector<pair<int,int>> ma[N];
vector<ll> dp[N][2];
// either we edge edge itself
map<int,ll> sm[N];
bool vis[N];
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>p[i];
        ma[a[i]].push_back({c[i],i});
        ma[b[i]].push_back({c[i],i});
    }
    for(int i=1;i<=n;i++)
    {
        sort(begin(ma[i]),end(ma[i]));
        dp[i][0].resize(ma[i].size()+2,1e18);
        dp[i][1].resize(ma[i].size()+2,1e18);
        for(auto tlx:ma[i])
        {
            sm[i][tlx.first]+=p[tlx.second];
        }
    }
    priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>pq;
    for(int i=0;i<ma[1].size();i++)
    {
        dp[1][0][i]=0;
        pq.push({0,1,0,i});
    }
    while(pq.size()>0)
    {
        auto it=pq.top();
        pq.pop();
        int x=it[1],j=it[3],dt=it[0],chg=it[2];
        // cout<<dt<<' '<<x<<' '<<chg<<' '<<j<<endl;
        if(dt!=dp[x][chg][j])
        {
            continue;
        }
        int uid=ma[x][j].second,col=ma[x][j].first;
        for(int tlx=0;tlx<ma[x].size();tlx++)
        {
            if(tlx==j)continue;
            int c=ma[x][tlx].first,id=ma[x][tlx].second;
            int oth=a[id]+b[id]-x,idp=lower_bound(begin(ma[oth]),end(ma[oth]),ma[x][tlx])-begin(ma[oth]);
            int nc=dt+(sm[x][c]-p[id]-p[uid]*(col==c)*(chg)); // no change in current edge

            if(dp[oth][0][idp]>nc)
            {
                dp[oth][0][idp]=nc;
                pq.push({nc,oth,0,idp});
            }

            // change current edge
            nc=dt+p[id];
            if(dp[oth][1][idp]>nc)
            {
                dp[oth][1][idp]=nc;
                pq.push({nc,oth,1,idp});
            }
        }
    }
    ll ans=1e18;
    for(int j=0;j<ma[n].size();j++)ans=min(ans,dp[n][0][j]);
    for(int j=0;j<ma[n].size();j++)ans=min(ans,dp[n][1][j]);
    if(ans==1e18)ans=-1;
    cout<<ans<<endl;
}

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