Submission #1044242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044242		Otalp	Robot (JOI21_ho_t4)	C++14	0 / 100	1483 ms	145880 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second


vector<pii> q[200100];
pii d[200100];
map<int, int> dd[200100];
map<int, vector<pii>> dq[200100];
map<int, ll> dp[200100];
map<int, int> us[200100];


void solve(){
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int l, r, x, c;
        cin>>l>>r>>x>>c;
        q[l].pb({r, i});
        q[r].pb({l, i});
        d[i] = {x, c};
    }
    for(int i=1; i<=n; i++){
        for(pii h: q[i]){
            int to = h.ff;
            int e = h.ss;
            dd[i][d[e].ff] += d[e].ss;
            dq[i][d[e].ff].pb(h);
        }
    }
    set<pair<ll, pii>> s;
    s.insert({0, {1, 0}});
    while(s.size()){
        auto it = s.begin();
        int v = it -> ss.ff, k = it -> ss.ss;
        if(us[v][k]){
            s.erase(s.begin());
            continue;
        }
        us[v][k] = 1;
        dp[v][k] = it -> ff;
        //cout<<v<<' '<<k<<' '<<dp[v][k]<<'\n';
        s.erase(it);
        if(k == 0){
            for(pii h: q[v]){
                int to = h.ff;
                int c = d[h.ss].ff;
                int g = d[h.ss].ss;
                s.insert({dp[v][k] + dd[v][c] - g, {to, 0}});
                s.insert({dp[v][k] + dd[to][c], {to, c}});
                s.insert({dp[v][k] + g, {to, 0}});
            }
        }
        else{
            for(pii h: dq[v][k]){
                int to = h.ff;
                int c = d[h.ss].ff;
                int g = d[h.ss].ss;
                s.insert({dp[v][k] - g, {to, 0}});
                s.insert({dp[v][k] - g + dd[to][c], {to, c}});
                s.insert({dp[v][k] + g, {to, 0}});
            }
        }
    }
    ll ans = 1e18;
    for(int i=0; i<=m; i++){
        if(us[n][i]) ans = min(ans, dp[n][i]);
    }
    if(ans == 1e18) cout<<-1;
    else cout<<ans;




            
    

        


}

signed main(){
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:30:17: warning: unused variable 'to' [-Wunused-variable]
   30 |             int to = h.ff;
      |                 ^~

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