Submission #990180

#	Time	Username	Problem	Language	Result	Execution time	Memory
990180		KietJ	Robot (JOI21_ho_t4)	C++17	0 / 100	445 ms	36376 KiB

Main

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

#define f first
#define s second
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair <int, int> ii;

const int N = 2e5 + 1;
const int mod = 998244353;

struct datas {
    int ver, c, d;
};

vector <datas> ed[N];

void solve() {
    int n, m; cin >> n >> m;
    map <ii, ll> sve;
    for(int i = 0; i < m; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        ed[u].push_back({v, c, d});
        ed[v].push_back({u, c, d});
        sve[{u, c}] += d;
        sve[{v, c}] += d;
    }

    priority_queue <pair <ll, pair <map <ii, ll>, int>>, vector <pair <ll, pair <map <ii, ll>, int>>>, greater <pair <ll, pair <map <ii, ll>, int>>>> pq;
    vector <ll> dp(n + 1, 1e18);
    map <ii, ll> mp;  

    pq.push({0, {mp, 1}});
    dp[1] = 0;

    while (sz(pq)) {
        ll d = pq.top().f; 
        map <ii, ll> save = pq.top().s.f;
        int u = pq.top().s.s;
        pq.pop();
        if (dp[u] != d) continue;
        for(auto x: ed[u]) {
            int v = x.ver, c = x.c;
            ll _d = x.d;

            if (sve[{u, c}] - save[{u, c}] >= _d)
                _d = min(_d, sve[{u, c}] - save[{u, c}] - _d);

            if (dp[v] > dp[u] + _d) {
                map <ii, ll> _save;
                if (x.d == _d)
                    _save[{v, c}] += _d; 
                dp[v] = dp[u] + _d;
                pq.push({dp[v], {_save, v}});
            }
        }
    }

    cout << (dp[n] != 1e18 ? dp[n] : -1) << "\n";
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    // freopen("ROBOT.INP", "r", stdin);
    // freopen("ROBOT.OUT", "w", stdout);

    int t = 1;
    // cin >> t;

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

    return 0;
}

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