Submission #535756

#	Time	Username	Problem	Language	Result	Execution time	Memory
535756		sam571128	Robot (JOI21_ho_t4)	C++17	34 / 100	3029 ms	35232 KiB

Main

#include <bits/stdc++.h>
 
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
const int N = 1e5 + 5, M = 2e5 + 5;
struct edge {
    int v, c, p;
};
 
map<pair<int,int>,int> dp;
vector<edge> adj[N];
int sum[M];

bool add(pair<int,int> p, int val){
    if(!dp.count(p)){
        dp[p] = val;
        return true;
    }else if(dp[p] > val){
        dp[p] = val;
        return true;
    }
    return false;
}
 
signed main() {
    fastio
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        adj[u].push_back({v, c, p});
        adj[v].push_back({u, c, p});
    }
 
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
    dp[{1,0}] = 0;
    pq.push({0, {1, 0}});
    //dis, vertex, lst
 
    while (!pq.empty()) {
        auto [ww, pp] = pq.top();
        pq.pop();
        auto [u, lst] = pp;
        if(ww > dp[{u,lst}]) continue;
 
        for (auto [v, c, p] : adj[u]){
            if(v == lst) p = 0;
            sum[c] += p;
        }
 
        for (auto [v, c, p] : adj[u]) {
            if(v == lst) p = 0;
            //Dont change this edge, change all others
            if(add({v,0},dp[{u,lst}] + sum[c] - p)) {
                pq.push({dp[{v,0}], {v, 0}});
            }
 
            //Change this edge, using p
            if(add({v,u},dp[{u,lst}]+p)){
                pq.push({dp[{v,u}], {v, u}});
            }
        }
 
        for (auto [v, c, p] : adj[u]){
            if(v == lst) p = 0;
            sum[c] -= p;
        }
    }
 
    int ans = 1e18;
 
    for (int i = 0; i <= m; i++) {
        if(dp.count({n,i})) ans = min(ans, dp[{n,i}]);
    }
 
    cout << (ans == 1e18 ? -1 : ans) << "\n";
}

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