Submission #1295868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295868		notbraining	Robot (JOI21_ho_t4)	C++20	100 / 100	867 ms	82552 KiB

Main

//#pragma GCC optimize ("O3")
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#include <cassert>
#include<algorithm>
#include <cstring>
#include<unordered_set>
#include<queue>
#include <array>
#include<cmath>
#include<unordered_map>
#include<queue>
#include <list>
#include <bitset>
using namespace std;
#define int long long
#define pii pair<int,int>
#define LL long long
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt”)
int INF = 1e18;
int n, m;
struct edge{
    int destination, color_of_edge, price;
};
int dp[100001];
map<int, vector<edge>> adj[100001];
map<int, int> dp2[100001], colored_sum[100001];
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    // adj = vector<vector<edge>>(n);
    memset(dp, 0x3f, sizeof dp);
    for(int i = 0; i < m; ++i){
        int a, b, col, p;
        cin >> a >> b >> col >> p;
        --a;
        --b;
        adj[a][col].push_back({b, col, p});
        adj[b][col].push_back({a, col, p});
        colored_sum[a][col] += p;
        colored_sum[b][col] += p;
    }
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>>pq;
    //dist, node, color of last edge recolored to reach here, IF YOU ARE IN DIST2 (if none that just 0 )
    dp[0] = 0;
    pq.push({0, {0, 0}});
    while(!pq.empty()){
        int d = pq.top().first;
        auto [node, color_edge] = pq.top().second;
        pq.pop();
        if(color_edge == 0){
            //normal dist 
            if(d > dp[node])
                continue;
            for(auto& i : adj[node]){
                for(auto [dest, col, p] : i.second){
                    int takeneighbors = colored_sum[node][col] - p; //take neighbors
                    if(dp[dest] > d + takeneighbors){
                        dp[dest] = d + takeneighbors;
                        pq.push({dp[dest], {dest, 0}});
                    }
                    int takeyou = p;
                    if(dp[dest] > d + takeyou){
                        dp[dest] = d + takeyou;
                        pq.push({dp[dest], {dest, 0}});
                    }
                    if(!dp2[dest].count(col) || dp2[dest][col] > d){
                        dp2[dest][col] = d;
                        pq.push({dp2[dest][col], {dest, col}});
                    }

                }
            }

        } else{
            //dist2
            if(d > dp2[node][color_edge])
                continue;
            //must take all neighbors except one

            for(auto [dest, col, p] : adj[node][color_edge]){

                int takeneighbors = colored_sum[node][col] - p;
                if(dp[dest] > d + takeneighbors){
                    dp[dest] = d + takeneighbors;
                    pq.push({dp[dest], {dest, 0}});
                }
            }
        }
    }
    if(dp[n - 1] > INF){
        cout << -1;
        return 0;
    }
    cout << dp[n - 1];
    //find ans for dp[n-1]
}

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