제출 #990175

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990175		KietJ	Robot (JOI21_ho_t4)	C++17	0 / 100	683 ms	51880 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, int> mark, 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;
        mark[{u, c}]++;
        mark[{v, c}]++;
    }

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

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

    while (sz(pq)) {
        ll d = pq.top().f; 
        map <ii, int> 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, _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, int> _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);

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

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

    return 0;
}

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