Submission #379870

#	Time	Username	Problem	Language	Result	Execution time	Memory
379870		doowey	Robot (JOI21_ho_t4)	C++14	100 / 100	2132 ms	174824 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 100;

map<int, vector<pii>> E[N];
map<int, ll> cum[N];

map<int, ll> dp[N][2];
map<int, bool> proc[N][2];
int cnt[N];
bool any[N];

struct state{
    int node;
    ll distance;
    int mode;
    int color;
    bool operator< (const state &aq) const {
        return distance > aq.distance;
    }
};

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    int ui, vi, ci, pi;
    for(int i = 1; i <= m; i ++ ){
        cin >> ui >> vi >> ci >> pi;
        E[ui][ci].push_back(mp(vi, pi));
        E[vi][ci].push_back(mp(ui, pi));
        cum[ui][ci] += pi;
        cum[vi][ci] += pi;
    }
    priority_queue<state> pq;
    pq.push({1, 0ll, 0ll, 0ll});
    dp[1][0][0] = 0;
    int node;
    ll dis;
    int mode;
    int colr;
    ll gg;
    while(!pq.empty()){
        node = pq.top().node;
        dis = pq.top().distance;
        mode = pq.top().mode;
        colr = pq.top().color;
        pq.pop();
        if(proc[node][mode][colr]) continue;
        proc[node][mode][colr] = true;
        if(mode == false){
            if(node == n){
                cout << dis << "\n";
                return 0;
            }
            if(cnt[node] == 2) continue;
            cnt[node] ++ ;
            for(auto x : E[node]){
                for(auto y : x.se){
                    gg = dis + y.se;
                    if(!dp[y.fi][0].count(x.fi) || dp[y.fi][0][x.fi] > gg){
                        dp[y.fi][0][x.fi] = gg;
                        pq.push({y.fi, gg, 0, 0});
                    }
                    gg = dis;
                    if(!dp[y.fi][1].count(x.fi) || dp[y.fi][1][x.fi] > gg){
                        dp[y.fi][1][x.fi] = gg;
                        pq.push({y.fi, gg, 1, x.fi});
                    }
                    if(x.fi != colr){
                        gg = dis + cum[node][x.fi] - y.se;
                        if(!dp[y.fi][0].count(x.fi) || dp[y.fi][0][x.fi] > gg){
                            dp[y.fi][0][x.fi] = gg;
                            pq.push({y.fi, gg, 0, x.fi});
                        }
                    }
                }
            }
        }
        else{
            gg = dis + cum[node][colr];
            for(auto x : E[node][colr]){
                if(!dp[x.fi][0].count(colr) || dp[x.fi][0][colr] > gg - x.se){
                    dp[x.fi][0][colr] = gg - x.se;
                    pq.push({x.fi, gg - x.se, 0, colr});
                }
            }
        }
    }
    cout << "-1\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:8:12: warning: narrowing conversion of 'y.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define fi first
      |            ^
Main.cpp:73:36: note: in expansion of macro 'fi'
   73 |                         pq.push({y.fi, gg, 0, 0});
      |                                    ^~
Main.cpp:8:12: warning: narrowing conversion of 'y.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define fi first
      |            ^
Main.cpp:78:36: note: in expansion of macro 'fi'
   78 |                         pq.push({y.fi, gg, 1, x.fi});
      |                                    ^~
Main.cpp:8:12: warning: narrowing conversion of 'y.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define fi first
      |            ^
Main.cpp:84:40: note: in expansion of macro 'fi'
   84 |                             pq.push({y.fi, gg, 0, x.fi});
      |                                        ^~
Main.cpp:8:12: warning: narrowing conversion of 'x.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define fi first
      |            ^
Main.cpp:95:32: note: in expansion of macro 'fi'
   95 |                     pq.push({x.fi, gg - x.se, 0, colr});
      |                                ^~

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