제출 #1158921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158921		Marco_Escandon	Robot (JOI21_ho_t4)	C++20	34 / 100	3049 ms	1456644 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
vector<vector<pair<ll,ll>>> cad;
map<ll,vector<pair<ll,ll>>> cad2[(ll)1e5+5];
vector<map<ll,ll>> c2;
vector<pair<ll,ll>> E;
ll n,m;
struct st{
    ll cost,node,ed;
    friend bool operator < (st a, st b)
    {
        return a.cost>b.cost;
    }
};
ll cmc()
{
    vector<map<ll,ll>> v(cad.size()),v2(cad.size());
    priority_queue<st>q;q.push({1,1,(ll)m+1});
    while(!q.empty())
    {
        st temp=q.top();q.pop();
        //cerr<<temp.node<<" "<<temp.cost-1<<"\n";
        if(temp.ed==m+1)
        {
            if(v[temp.node][temp.ed]==0)
            {
                if(temp.node==n) return temp.cost-1;
                v[temp.node][temp.ed]=temp.cost;
                for(auto i:cad[temp.node])
                {
                    ll cnt=c2[temp.node][E[i.y].x]-E[i.y].y;
                    if(E[temp.ed].x==E[i.y].x)
                        cnt-=E[temp.ed].y;
                    if(v2[i.x][m+1]==0||temp.cost+min(cnt,E[i.y].y)<v2[i.x][m+1]==0)
                    { 
                        q.push({temp.cost+min(cnt,E[i.y].y),i.x,(ll)m+1});  
                    }
                    if(v2[i.x][i.y]==0||temp.cost+E[i.y].y<v2[i.x][i.y])
                    {
                        q.push({temp.cost+E[i.y].y,i.x,i.y});
                    }
                }
            }
        }
        else if(v[temp.node][temp.ed]==0)
        {
            if(temp.node==n) return temp.cost-1;
            v[temp.node][temp.ed]=temp.cost;
            for(auto i:cad2[temp.node][E[temp.ed].x])
            {
                ll cnt=c2[temp.node][E[i.y].x]-E[i.y].y;
                if(E[temp.ed].x==E[i.y].x)
                    cnt-=E[temp.ed].y;
                    if(v2[i.x][m+1]==0||temp.cost+min(cnt,E[i.y].y)<v2[i.x][m+1]==0)
                    { 
                        q.push({temp.cost+min(cnt,E[i.y].y),i.x,(ll)m+1});  
                    }
                    if(v2[i.x][i.y]==0||temp.cost+E[i.y].y<v2[i.x][i.y])
                    {
                        q.push({temp.cost+E[i.y].y,i.x,i.y});
                    }
            }
        }
    }
    return 1e16;
}
int main()
{
  
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    cad.resize(n+1);
    c2.resize(n+1);
    E.resize(m+2);
    for(int i=0; i<m; i++)
    {
        ll a,b;
        cin>>a>>b>>E[i].x>>E[i].y;
        cad[a].push_back({b,i});
        cad[b].push_back({a,i});
        c2[a][E[i].x]+=E[i].y;
        c2[b][E[i].x]+=E[i].y;
        cad2[a][E[i].x].push_back({b,i});
        cad2[b][E[i].x].push_back({a,i});
    }
    ll t1=cmc();
    if(t1==1e16) t1=-1;
    cout<<t1; 
}

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