Submission #1269823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269823		ducanh0811	Robot (JOI21_ho_t4)	C++20	58 / 100	3095 ms	117184 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

#define MAXN 100005
#define MAXM 200005
int n, m;
struct edge {
    int v, c, p;
};
vector<edge> g[MAXN];
map<int, vector<edge>> specG[MAXN];
int dp1[MAXN];
map<int, int> dp2[MAXN];
map<int, bool> visited_dp2[MAXN];
map<int, int> sump[MAXN];

struct club {
    int w, u, c;
};

struct CMP {
    bool operator() (const club &a, const club &b) const{
        return a.w > b.w;
    }
};

void solve(){
    cin >> n >> m;
    FOR(i, 1, m){
        int u, v, c, p; cin >> u >> v >> c >> p;
        g[u].push_back({v, c, p});
        g[v].push_back({u, c, p});
        specG[u][c].push_back({v, c, p});
        specG[v][c].push_back({u, c, p});
        sump[u][c] += p;
        sump[v][c] += p;
    }
    priority_queue<club, vector<club>, CMP> pq;
    memset(dp1, 0x3f, sizeof dp1);
    dp1[1] = 0;
    pq.push({0, 1, 0});
    while (pq.size()){
        auto [w, u, c] = pq.top();
        pq.pop();
        if (c == 0){
            for (edge &x : g[u]){
                auto [V, C, P] = x;
                int minVal = 1e15;
                // case 1: change this edge's color and go
                minVal = min(minVal, w + P);
                // case 2: change the color of all other edges that have the same color with this edge
                minVal = min(minVal, w + sump[u][C] - P);

                if (dp1[V] > minVal){
                    dp1[V] = minVal;
                    pq.push({dp1[V], V, 0});
                }

                // case 3: become a GOD (using dp2)

                if (visited_dp2[V][C] == 0){
                    visited_dp2[V][C] = 1;
                    dp2[V][C] = 1e15;
                }

                minVal = w;
                if (dp2[V][C] > minVal){
                    dp2[V][C] = minVal;
                    pq.push({dp2[V][C], V, C});
                }

            }
        } else {
            // turn off GOD mode (dp2 -> dp1)
            for (edge &x : specG[u][c]){
                auto [V, C, P] = x;
                int minVal = w + sump[u][C] - P;
                if (dp1[V] > minVal){
                    dp1[V] = minVal;
                    pq.push({dp1[V], V, 0});
                }
            }
        }
    }
    if (dp1[n] > 1e15) dp1[n] = -1;
    cout << dp1[n];
}

#define task ""
int32_t main(){
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    return 0;
}

Compilation message (stderr)

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

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