Submission #1153392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153392		ALTAKEXE	Robot (JOI21_ho_t4)	C++20	24 / 100	218 ms	21536 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define INF INT_MAX
#define all(x) x.begin(),x.end()
const int MOD = 1e9+7;
using namespace std;
struct T {
    ll to, color, cost;
};
ll n, m;
vector<vector<T>> adj;
vector<ll> dist, sum, best;
const ll inf = 1e18;
void solve(){
    cin >> n >> m;
    adj.resize(n + 1);
    dist.resize(n + 1, inf);
    best.resize(m + 1, inf);
    sum.resize(m + 1, 0);
    for (ll i = 0; i<m; ++i) {
        ll u, v, color, cost;
        cin >> u >> v >> color >> cost;
        T a = {v, color, cost};
        T b = {u, color, cost};
        adj[u].push_back(a);
        adj[v].push_back(b);
    }
    priority_queue<pair<ll, ll>> pq;
    dist[1] = 0;
    pq.push({0, 1});

    vector<bool> visited(n + 1, false);

    while (!pq.empty()) {
        ll u = pq.top().second;
        ll curr = -pq.top().first;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (T &e : adj[u]) {
            sum[e.color] = 0;
            best[e.color] = inf;
        }

        for (T &e : adj[u]) {
            sum[e.color] += e.cost;
            best[e.color] = min(best[e.color], dist[e.to]);
        }

        for (T &e : adj[u]) {
            ll color = e.color;
            ll v = e.to;
            ll cost = e.cost;
            ll w = min(cost, sum[color] - cost);

            if (dist[v] > curr + w) {
                dist[v] = curr + w;
                pq.push({-dist[v], v});
            }
            if (dist[v] > best[color] + sum[color] - w) {
                dist[v] = best[color] + sum[color] - w;
                pq.push({-dist[v], v});
            }
        }

        for (T &e : adj[u]) {
            sum[e.color] = 0;
            best[e.color] = inf;
        }
    }
    cout<< (dist[n] == inf ? -1 : dist[n])<<"\n";
}
int main()
{
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

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