Submission #936731

#	Time	Username	Problem	Language	Result	Execution time	Memory
936731		anton	Robot (JOI21_ho_t4)	C++17	0 / 100	77 ms	14416 KiB

Main

    #include<bits/stdc++.h>

    using namespace std;
    #define int long long
    #define pii pair<int, int>

    const int MAX_N=  1e5;

    map<int, vector<pii>> adj[MAX_N];


    int n, m;
    int dijkstra(){
        map<pii, int> dist;
        priority_queue<pair<int, pii>> pq;

        pq.push({0, {0, -1}});
        dist[{0, -1}] = 0;

        while(pq.size()>0 && pq.size()<20){
            auto cur= pq.top();
            //cout<<-cur.first<<" "<<cur.second.first<<" "<<cur.second.second<<endl;
            pq.pop();
            int cdist = -cur.first;
            pii pos = cur.second;
            if(cdist==dist[pos]){
                for(auto color: adj[pos.first]){
                    int cost = 0;
                    int nb= 0;
                    for(auto edge: color.second){
                        if(edge.first!= pos.second){
                            cost += edge.second;
                            nb++;
                        }
                    }
                    //cout<<color.first<<" cost "<<cost<<endl;
                    if(nb>1){
                        //cout<<color.first<<" multiple "<<endl;
                        for(auto edge: color.second){
                            int next = min(cdist+edge.second, cdist + cost - edge.second);
                            if(edge.first!=pos.second && (dist.find({edge.first, pos.first})== dist.end()|| dist[{edge.first, pos.first}]>next)){
                                //cout<<edge.first<<" "<<pos.second<<endl;
                                //cout<<cdist<<" "<<cost<<" "<<edge.second<<endl;
                                dist[{edge.first, pos.first}] = next;
                                pq.push({-(next), {edge.first, pos.first}});
                            }
                        }
                    }
                    else{
                        //cout<<color.first<<" single "<<endl;
                        for(auto edge: color.second){
                            if(edge.first!=pos.second && (dist.find({edge.first, -1})== dist.end()|| dist[{edge.first, -1}]>cdist)){
                                //cout<<edge.first<<" "<<pos.second<<endl;
                                //cout<<cdist<<" "<<cost<<" "<<edge.second<<endl;
                                dist[{edge.first, -1}] = cdist;
                                pq.push({-(cdist), {edge.first, -1}});
                            }
                        }
                    }

                }
            }
        }
        int res= 1e18;
        for(int i = -1; i<n; i++){
            if(dist.find({n-1, i})!=dist.end()){
                res= min(res, dist[{n-1, i}]);
            }
        }
        if(res== 1e18){
            return -1;
        }
        return res;
        
    }

    signed main(){
        cin>>n>>m;

        for(int i = 0; i<m; i++){
            int a, b, c, d;
            cin>>a>>b>>c>>d;
            adj[a-1][c].push_back({b-1, d});
            adj[b-1][c].push_back({a-1, d});
        }

        cout<<dijkstra()<<endl;
    }

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