oj.uz

Submission #936727

# Submission time Handle Problem Language Result Execution time Memory
936727 2024-03-02T15:45:05 Z anton Robot (JOI21_ho_t4) C++17
0 / 100
 97 ms 15804 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;
                for(auto edge: color.second){
                    if(edge.first!= pos.second){
                        cost += edge.second;
                    }
                }
                //cout<<color.first<<" cost "<<cost<<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}});
                    }
                }

            }
        }
    }
    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 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 5136 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 97 ms 15804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

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