Submission #1124057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124057		Yang8on	Robot (JOI21_ho_t4)	C++20	100 / 100	1170 ms	76748 KiB

Main

#include <bits/stdc++.h>
#define Y8o "Robot"
#define maxn (int) 1e5 + 5
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define all(x) x.begin(), x.end()
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define fi(i, a, b) for(int i = a; i <= b; i ++)
#define fid(i, a, b) for(int i = a; i >= b; i --)

//#define f first
//#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

const ll inf = (1ll << 60);

int n, m;
map<int, vector<pii>> o[maxn];
map<int, ll> sum[maxn], last_dp[maxn];
ll dp[maxn];

void solve() {
    cin >> n >> m ;
    fi(i, 1, m) {
        int u, v, c, w; cin >> u >> v >> c >> w;
        o[u][c].push_back({ v, w }), o[v][c].push_back({ u, w });
        sum[u][c] += w, sum[v][c] += w;
    }

    memset(dp, 0x3f, sizeof dp);
    priority_queue<tuple<ll, int, int>> q;

    dp[1] = 0;
    q.push({ -dp[1], 1, 0 });

    while(q.size()) {
        auto [val, u, last_color] = q.top(); q.pop();
        val = -val;

        if(!last_color) {
            if(val > dp[u]) continue;

            for(auto x : o[u]) {
                int color = x.first; ll total = sum[u][color];

                for(auto [v, w] : x.second) {
                    /// change this edge
                    if(dp[v] > val + w) {
                        dp[v] = val + w;
                        q.push({ -dp[v], v, 0 });
                    }

                    /// change other edges with same color
                    if(dp[v] > val + total - w) {
                        dp[v] = val + total - w;
                        q.push({ -dp[v], v, 0 });
                    }

                    /// keep this edge to prepare for nex(v) of v
                    if(last_dp[v].find(color) == last_dp[v].end() || last_dp[v][color] > val) {
                        last_dp[v][color] = val;
                        q.push({ -last_dp[v][color], v, color });
                    }
                }
            }
        }
        else {
            int color = last_color; ll total = sum[u][color];
            for(auto [v, w] : o[u][color]) {
                if(dp[v] > val + total - w) {
                    dp[v] = val + total - w;
                    q.push({ -dp[v], v, 0 });
                }
            }
        }
    }

    cout << (dp[n] >= inf ? -1 : dp[n]);
}


int main() {
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void iof()':
Main.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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