Submission #1025821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025821		underwaterkillerwhale	Robot (JOI21_ho_t4)	C++17	100 / 100	902 ms	95168 KiB

Main

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 1e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e18;
const int BASE = 1337;

int n, m;
map<int,ll> dp[N], cost[N];
map<int, vector<pair<int, ll>>> ke[N];

void solution () {
    cin >> n >> m;
    rep (i, 1, m) {
        ll u, v, c, p;
        cin >> u >> v >> c >> p;
        ke[u][c].push_back({v, p});
        ke[v][c].push_back({u, p});
        cost[u][c] += p;
        cost[v][c] += p;
        dp[u][c] = INF;
        dp[v][c] = INF;
    }
    rep (i, 1, n) dp[i][0] = INF;
    struct Node {
        ll u, c, val;
    };
    struct cmp {
        bool operator () (Node A, Node B) { return A.val > B.val; }
    };
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({1, 0, 0});
    dp[1][0] = 0;
    while (!pq.empty()) {
        int u = pq.top().u, c = pq.top().c;
        ll val = pq.top().val;
        pq.pop();
        if (u == n && c == 0) break;
        if (c) {
            if (val != dp[u][c]) continue;
            iter (&id, ke[u][c]) {
                ll v, w;
                tie(v, w) = id;
                if (dp[v][0] > dp[u][c] + cost[u][c] - w){
                    dp[v][0] = dp[u][c] + cost[u][c] - w;
                    pq.push({v, 0, dp[v][0]});
                }
            }
        }
        else {
            if (val != dp[u][0]) continue;
            iter (&id2, ke[u]) {
                int vc = id2.fs;
                iter (&id, id2.se) {
                    ll v, w;
                    tie(v, w) = id;
                    if (dp[v][vc] > dp[u][0]) {
                        dp[v][vc] = dp[u][0];
                        pq.push({v, vc, dp[v][vc]});
                    }
                    if (dp[v][0] > dp[u][0] + w) {
                        dp[v][0] = dp[u][0] + w;
                        pq.push({v, 0, dp[v][0]});
                    }
                    if (dp[v][0] > dp[u][0] + cost[u][vc] - w) {
                        dp[v][0] = dp[u][0] + cost[u][vc] - w;
                        pq.push({v, 0, dp[v][0]});
                    }
                }
            }
        }
    }
    if (dp[n][0] == INF)
        cout << -1 <<"\n";
    else
        cout << dp[n][0] <<"\n";
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13

*/

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