Submission #974679

#	Time	Username	Problem	Language	Result	Execution time	Memory
974679		berr	Robot (JOI21_ho_t4)	C++17	100 / 100	789 ms	91296 KiB

Main

#include <bits/stdc++.h>
using namespace std; 
#define int long long
const int N=5005, INF=1e18;
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   
    int n, m; cin >> n >> m;
 
    vector<vector<array<int, 2>>> g(n);
    vector<int> c(m), p(m), u(m), v(m);
    map<int, int> s[n], dpp[n], pos[n];
    vector<int> dp(n, INF);

    for(int i=0; i<m; i++){
        cin >> u[i] >> v[i] >> c[i] >> p[i];
        u[i]--; v[i]--;
        if(u[i] > v[i]) swap(u[i], v[i]);
        g[u[i]].push_back({v[i], i});
        g[v[i]].push_back({u[i], i});
        s[u[i]][c[i]]+=p[i];
        s[v[i]][c[i]]+=p[i];

    }
        
    for(int i=0; i<n; i++){
        if(!g[i].size()) continue;
        sort(g[i].begin(), g[i].end(), [&](auto x, auto y){
            return c[x[1]] < c[y[1]];
        });

        for(int l=0; l<g[i].size(); l++){
            int col=c[g[i][l][1]];
            if(pos[i].count(col)) continue;
            pos[i][col] = l;
        }
    }

    priority_queue<array<int, 3>> pq;
    dp[0]=0;
    pq.push({0, 0, -1});
    int ans = INF;

    while(pq.size()){
        auto [cost, v, color] = pq.top();

        pq.pop(); cost*=-1;
       // cout<<cost<<" "<<v<<" "<<color<<"\n";
        if(v==n-1){
            ans=min(ans, cost);
        }

        if(color == -1){
            if(dp[v] != cost) continue;

            for(auto [i, j]: g[v]){
                if(dp[i] > cost+p[j]){
                    dp[i] = cost+p[j];
                    pq.push({-dp[i], i, -1});
                }
                if(dp[i] > cost+s[v][c[j]]-p[j]){
                    dp[i] = cost+s[v][c[j]]-p[j];
                    pq.push({-dp[i], i, -1});
                }
                if(!dpp[i].count(c[j]) || dpp[i][c[j]] > cost){
                    dpp[i][c[j]] = cost;
                    pq.push({-(cost), i, c[j]});
                }
            }
        }
        else{
            if(cost != dpp[v][color]) continue;

            for(int l=pos[v][color]; l<g[v].size(); l++){
                auto [i, j]=g[v][l];

                if(c[j] != color) break;
                else{
                    int val = cost+s[v][c[j]]-p[j];
                    if(dp[i] > val){
                        dp[i] = val;
                        pq.push({-val, i, -1});
                    }
                }
            }
        }
    }

    if(dp[n-1] == INF) cout<<-1;
    else cout<<dp[n-1];
 
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:34:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int l=0; l<g[i].size(); l++){
      |                      ~^~~~~~~~~~~~
Main.cpp:76:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for(int l=pos[v][color]; l<g[v].size(); l++){
      |                                      ~^~~~~~~~~~~~

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