Submission #1257497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257497		Bui_Quoc_Cuong	Robot (JOI21_ho_t4)	C++20	100 / 100	566 ms	64984 KiB

Main

#include<bits/stdc++.h>
using namespace std;

template <class A, class B>
    bool mini(A &a, const B b) {
        if(a > b){
            a = b;
            return true;
        }
        return false;
    }

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a.size())

typedef pair <int, int> pii;
typedef long long ll;
typedef vector <int> vi;

const int N = 3e5 + 5;
const int oo = 2e9;
const int MOD = 1e9 + 7;
const long long INF = 1e18;

int n, m;
vector <array <int, 3>> g[N];
array <int, 4> E[N];

struct Data{
    int u, t;
    long long cost;
    bool operator <(const Data &x) const{
        return cost > x.cost;
    }
}; priority_queue <Data, vector <Data>> pq;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define taskname "r25robot12"
    if(fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    cin >> n >> m;
    vector <map <int, long long>> sum_c(n + 2);
    vector <map <int, long long>> dp(n + 2);
    FOR(i, 1, m){
        int u, v, c, p; cin >> u >> v >> c >> p;
        g[u].push_back({c, v, p}); g[v].push_back({c, u, p});
        sum_c[u][c]+= p;
        sum_c[v][c]+= p;
        E[i] = {u, v, c, p};
    }

    dp[1][0] = 0;
    pq.push({1, 0, 0});
    FOR(i, 1, n) sort(g[i].begin(), g[i].end());

    while(!pq.empty()){
        auto [u, t, cost] = pq.top();
        pq.pop();
        if(cost != dp[u][t]) continue;

        if(t == 0){
            for(auto [c, v, p] : g[u]){
                if(!dp[v].count(c)) dp[v][c] = 1e18;
                if(!dp[v].count(0)) dp[v][0] = 1e18;

                if(t == 0){
                    if(dp[v][0] > cost + min(1LL * sum_c[u][c] - p, 1LL * p)){
                        dp[v][0] = cost + min(1LL * sum_c[u][c] - p, 1LL * p);
                        pq.push({v, 0, dp[v][0]});
                    }
                    if(dp[v][c] > cost){
                        dp[v][c] = cost;
                        pq.push({v, c, dp[v][c]});
                    }
                }
            }
        } else{
            for(auto it = lower_bound(g[u].begin(), g[u].end(), array <int, 3> {t, 0, 0}); it != g[u].end(); it++){
                auto [c, v, p] = *it;
                if(c != t) break;
                if(!dp[v].count(0)) dp[v][0] = 1e18;

                if(dp[v][0] > cost + sum_c[u][c] - p){
                    dp[v][0] = cost + sum_c[u][c] - p;
                    pq.push({v, 0, dp[v][0]});
                }
            }
        }
    }
    if(dp[n].count(0) == 0 || dp[n][0] == 1e18) cout << - 1;
    else cout << dp[n][0];
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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