Submission #1269881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269881		dhuyyyy	Robot (JOI21_ho_t4)	C++20	100 / 100	1114 ms	118592 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using aa = array<int,3>;
using ii = pair<int,int>;

const int N = 2e5+5;

int n, m, u, v, c, kc, p, dp[N];

map<int,int> dp2[N],sum[N];
map<int,vector<aa>> adj[N];

priority_queue<aa,vector<aa>,greater<aa>> pq;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> u >> v >> c >> p;
        adj[u][c].push_back({v,p,c});
        adj[u][0].push_back({v,p,c});
        adj[v][c].push_back({u,p,c});
        adj[v][0].push_back({u,p,c});
        sum[u][c] += p;
        sum[v][c] += p;
        dp2[u][c] = dp2[v][c] = 1e18;
    }
    for (int i = 1; i <= n; i++) dp[i] = 1e18;
    dp[1] = 0;
    pq.push({0,1,0});
    while (!pq.empty()){
        aa it = pq.top();
        pq.pop();
        kc = it[0];
        u = it[1];
        c = it[2];
        if (!c){
            if (kc > dp[u]) continue;
            for (aa it : adj[u][0]){
                int mx = min(it[1],sum[u][it[2]] - it[1]);
                if (dp[it[0]] > dp[u] + mx){
                    dp[it[0]] = dp[u] + mx;
                    pq.push({dp[it[0]],it[0],0});
                }
                if (dp2[it[0]][it[2]] > dp[u]){
                    dp2[it[0]][it[2]] = dp[u];
                    pq.push({dp[u],it[0],it[2]});
                }
            }
        } else{
            if (kc > dp2[u][c]) continue;
            for (aa it : adj[u][c]){
                int mx = kc + sum[u][c] - it[1];
                if (dp[it[0]] > mx){
                    dp[it[0]] = mx;
                    pq.push({mx,it[0],0});
                }
            }
        }
    }
    cout << (dp[n] == (int)1e18 ? -1 : dp[n]);
    return 0;
}

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