Submission #1158891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158891		Marco_Escandon	Robot (JOI21_ho_t4)	C++20	34 / 100	3077 ms	456116 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>> 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<map<ll,ll>> v(cad.size());
    priority_queue<st>q;q.push({1,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]==0)
        {
            if(temp.node==cad.size()-1) 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(v[i.x][E.size()-1]==0)
                q.push({temp.cost+cnt,i.x,(ll)E.size()-1});  
                if(v[i.x][i.y]==0)
                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);
    ll n,m;
    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;
    }
    ll t1=cmc();
    if(t1==1e16) t1=-1;
    cout<<t1; 
}

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