제출 #1126062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126062		codexistent	Robot (JOI21_ho_t4)	C++20	100 / 100	285 ms	21508 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define MAXM 200005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define f first
#define s second

ll n, m, d[MAXN], mn[MAXM], sm[MAXM];
vector<array<ll, 3>> e[MAXN];
bool vis[MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w, c;
        cin >> u >> v >> c >> w;
        e[u].push_back({v, w, c});
        e[v].push_back({u, w, c});
    }
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    fill(d, d+n+1, 1e18);
    d[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        ll D = pq.top().f;
        ll s = pq.top().s;
        pq.pop();
        if (vis[s]) continue;
        vis[s] = 1;
        for (auto i : e[s]) mn[i[2]] = 1e18, sm[i[2]] = 0;
        for (auto i : e[s]) sm[i[2]] += i[1];
        for (auto i : e[s]) mn[i[2]] = min(mn[i[2]], d[i[0]] + sm[i[2]]);
        for (auto i : e[s]) {
            if (d[i[0]] > min({d[s] + i[1], d[s] + sm[i[2]] - i[1], mn[i[2]] - i[1]})) {
                d[i[0]] = min({d[s] + i[1], d[s] + sm[i[2]] - i[1], mn[i[2]] - i[1]});
                pq.push({d[i[0]], i[0]});
            }
        }
    }
    cout << (d[n] > 1e15 ? -1 : d[n]) << '\n';
}

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