oj.uz

Submission #936729

# Submission time Handle Problem Language Result Execution time Memory
936729 2024-03-02T15:54:53 Z anton Robot (JOI21_ho_t4) C++17
0 / 100
 113 ms 14356 KB 
    #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){
                            if(edge.first!=pos.second && (dist.find({edge.first, pos.first})== dist.end()|| dist[{edge.first, pos.first}]>cdist + cost - edge.second)){
                                //cout<<edge.first<<" "<<pos.second<<endl;
                                //cout<<cdist<<" "<<cost<<" "<<edge.second<<endl;
                                dist[{edge.first, pos.first}] = cdist + cost - edge.second;
                                pq.push({-(cdist + cost - edge.second), {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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Incorrect 1 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 14356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Incorrect 1 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -