Submission #1158889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158889		Marco_Escandon	Robot (JOI21_ho_t4)	C++20	34 / 100	3113 ms	484768 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;
                q.push({temp.cost-cnt,i.x,(ll)E.size()-1});  
                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; 
}
/*
13 21
7 10 4 
3 6 4 
8 10 4
3 9 2
1 4 4
2 6 4
3 11 2
3 8 16
8 11 16
6 10 4 
6 8 16
9 12 16
5 13 4
1 12 4
2 4 4
2 9 4
2 12 4
10 13 4
5 7 2
5 11 2
7 13 4 



13 21
1 4 4 5
2 4 4 18
1 12 4 7
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20
*/

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