oj.uz

Submission #936728

# Submission time Handle Problem Language Result Execution time Memory
936728 2024-03-02T15:50:38 Z anton Robot (JOI21_ho_t4) C++17
0 / 100
 98 ms 14420 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){
                    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{
                    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 = 0; 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 Incorrect 1 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

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

Subtask #3
0 / 42.0

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