Submission #485311

#	Time	Username	Problem	Language	Result	Execution time	Memory
485311		PurpleCrayon	Robot (JOI21_ho_t4)	C++17	0 / 100	427 ms	38276 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int MAXN = 1e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

int n, m;
vector<ar<int, 3>> input[MAXN];
vector<ar<int, 2>> adj[MAXN];
map<int, ll> sum[MAXN];
ll dist[MAXN];

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c, p; cin >> a >> b >> c >> p, --a, --b, --c;
        input[a].push_back({b, c, p}), input[b].push_back({a, c, p});
        sum[a][c] += p, sum[b][c] += p;
    }
    for (int a = 0; a < n; a++) {
        for (auto [b, c, p] : input[a]) {
            int cost = min((long long) p, sum[a][c] - p);

            adj[a].push_back({b, cost});
        }
        dist[a] = INF;
    }

    min_pq<pair<ll, int>> q; q.push({0, 0});
    dist[0] = 0;

    while (sz(q)) {
        auto [d, c] = q.top(); q.pop();
        if (d != dist[c]) continue;

        for (auto [nxt, w] : adj[c]) if (dist[nxt] > dist[c] + w) {
            dist[nxt] = dist[c] + w;
            q.push({dist[nxt], nxt});
        }
    }
    ll ans = dist[n-1];
    if (ans == INF) ans = -1;
    cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int T=1;
    // cin >> T;
    while (T--) solve();
}

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