Submission #1158890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158890		Marco_Escandon	Robot (JOI21_ho_t4)	C++20	34 / 100	3050 ms	484604 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;
vector<map<ll,ll>> c1,c2;
vector<pair<ll,ll>> E;
struct st{
    ll cost,node,ed;
    friend bool operator < (st a, st b)
    {
        return a.cost<b.cost;
    }
};
ll cmc()
{
    vector<unordered_map<ll,ll>> v(cad.size());
    for(int i=1; i<cad.size(); i++){
    v[i][E.size()-1]=1e16;
        for(int j=0; j<cad[i].size(); j++)
            v[i][cad[i][j].y]=1e16;}
    
    priority_queue<st>q;q.push({0,1,(ll)E.size()-1});
    while(!q.empty())
    {
        st temp=q.top();q.pop();
        //cerr<<temp.node<<" "<<temp.cost<<"\n";
        if(v[temp.node][temp.ed]==1e16)
        {
            if(temp.node==cad.size()-1) return -temp.cost;
            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(v[i.x][E.size()-1]==1e16)
                q.push({temp.cost-cnt,i.x,(ll)E.size()-1});  
                if(v[i.x][i.y]==1e16)
                q.push({temp.cost-E[i.y].y,i.x,i.y});
            }
        }
    }
    return 1e16;
}
int main()
{
    ll n,m;
    cin>>n>>m;
    cad.resize(n+1);
    c1.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});
        c1[a][E[i].x]++;
        c2[a][E[i].x]+=E[i].y;
        c1[b][E[i].x]++;
        c2[b][E[i].x]+=E[i].y;
    }
    ll t1=cmc();
    if(t1==1e16) t1=-1;
    cout<<t1; 
}

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