Submission #503548

#	Time	Username	Problem	Language	Result	Execution time	Memory
503548		InternetPerson10	Robot (JOI21_ho_t4)	C++17	0 / 100	141 ms	22168 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll BIG = 1234567891234567890;

vector<ll> min_cost;
vector<vector<pair<int, pair<ll, int>>>> adj; // {color, {cost, dest}}
vector<map<int, int>> ct;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; 
int lastUnique;

ll direct_robot(int n, vector<int> u, vector<int> v, vector<int> col, vector<ll> cost) {
    int m = u.size();
    lastUnique = m;
    adj.resize(n);
    ct.resize(n);
    min_cost.resize(n, BIG);
    for(int i = 0; i < m; i++) {
        adj[u[i]].push_back({col[i], {cost[i], v[i]}});
        adj[v[i]].push_back({col[i], {cost[i], u[i]}});
        ct[u[i]][col[i]]++;
        ct[v[i]][col[i]]++;
    }
    for(int i = 0; i < n; i++) {
        sort(adj[i].begin(), adj[i].end());
        for(int j = 0; j < adj[i].size(); j++) {
            bool ok = false;
            if(j == adj[i].size()-1) ok = true;
            else if(adj[i][j].first != adj[i][j+1].first) ok = true;
            if(ok) {
                ll tot_cost = 0;
                int k;
                for(k = j-1; k >= 0; k--) {
                    if(adj[i][k].first != adj[i][j].first) break;
                    tot_cost += adj[i][k].second.first;
                }
                for(k = j-1; k >= 0; k--) {
                    if(adj[i][k].first != adj[i][j].first) break;
                    int u_node, v_node, u_cost, v_cost;
                    tie(u_cost, u_node) = adj[i][j].second;
                    tie(v_cost, v_node) = adj[i][k].second;
                    adj[v_node].push_back({lastUnique++, {tot_cost, u_node}});
                }
                adj[i][j].second.first = min((ll)adj[i][j].second.first, tot_cost);
            }
        }
    }
    pq.push({0, 0});
    while(pq.size()) {
        pair<ll, int> p = pq.top();
        pq.pop();
        ll curr_cost;
        int curr_node;
        tie(curr_cost, curr_node) = p;
        if(min_cost[curr_node] != BIG) continue;
        min_cost[curr_node] = curr_cost;
        for(auto pa : adj[curr_node]) {
            int next_node;
            ll next_cost;
            tie(next_cost, next_node) = pa.second;
            next_cost += curr_cost;
            if(min_cost[next_node] != BIG) continue;
            pq.push({next_cost, next_node});
        }
    }
    return (min_cost[n-1] == BIG ? -1 : min_cost[n-1]); 
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m), col(m);
    vector<ll> cost(m);
    for(int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> col[i] >> cost[i];
        u[i]--;
        v[i]--;
        col[i]--;
    }
    cout << direct_robot(n, u, v, col, cost) << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'll direct_robot(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
Main.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int j = 0; j < adj[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             if(j == adj[i].size()-1) ok = true;
      |                ~~^~~~~~~~~~~~~~~~~~

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