Submission #936727

#	Time	Username	Problem	Language	Result	Execution time	Memory
936727		anton	Robot (JOI21_ho_t4)	C++17	0 / 100	97 ms	15804 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;
                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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42