Submission #487510

#	Time	Username	Problem	Language	Result	Execution time	Memory
487510		bigDuck	Robot (JOI21_ho_t4)	C++14	0 / 100	735 ms	45804 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
inline char get_ (){
    const int oo=1000005;
    static char buf[oo], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, oo, stdin), p1 == p2) ? EOF : *p1 ++;
}
int read_ () {
    char c = get_();
    int sum = 0;
    while(!(c >= '0' && c <= '9')) c = get_();
    while(c >= '0' && c <= '9') sum = sum * 10 + (c - '0'), c = get_();
    return sum;
}



int n, m;

vector<pair<int, pii>> g[100010];




map<pair<int, int>, int> csum;

map<pair<int, int>, pair<int, int>> dst;



int dijkstra(){


multiset<pair<pair<int, int>, pair<int, int>> > ms;
multiset<pair<int, int> > v;

ms.insert({{0, 0}, {1, 0} }  );


while(!ms.empty()){
    auto fr=ms.begin();

    int d=fr->ft.ft, mx=fr->ft.sc, nd=fr->sc.ft, c=fr->sc.sc;
    dst[{nd, c} ]={d, mx};
    v.insert( {nd, c} );
    ms.erase(ms.begin());
    if(nd==n){
        return d;
    }
    //cout<<d<<" "<<mx<<" "<<nd<<" "<<c<<"\n"<<flush;
    for(auto pr:g[nd]){
        int u=pr.ft, c2=pr.sc.ft, p=pr.sc.sc;
        if(v.find({u, c2} )!=v.end()){
            continue;
        }
        //cout<<"x"<<flush;
        auto it=ms.find( { dst[{u, c2}], {u, c2}  }   );
        if(  it!=ms.end()  ){
            if(dst[{u, c2}]>mp(d+csum[{nd, c2}]-p-( (c==c2)?(mx):(0ll) ), 0ll) ){
                if( (csum[{nd, c2}]-p-( (c==c2)?(mx):(0ll) ))>=0  ){
                ms.erase( it );
                ms.insert({{d+csum[{nd, c2}]-p-( (c==c2)?(mx):(0ll) ), 0ll}, {u, c2} } );
                }
            }
        }
        else{
            if( (csum[{nd, c2}]-p-( (c==c2)?(mx):(0ll) ))>=0  ){
                ms.insert({{d+csum[{nd, c2}]-p-( (c==c2)?(mx):(0ll) ), 0ll}, {u, c2} } );
            }
        }
        //cout<<"x"<<flush;
        if(v.find({u, m+1} )!=v.end()){
            continue;
        }

        it=ms.find( { dst[{u, m+1}], {u, m+1} } );
        if(it!=ms.end()){
            if(dst[{u, m+1}]>mp(d+p, p) ){
                ms.erase(it);
                ms.insert({ {d+p, p}, {u, m+1}  }  );
            }
        }
        else{
                ms.insert({ {d+p, p}, {u, m+1}  }  );
        }

    }


}



return -1;
}




int32_t main(){
INIT
cin>>n>>m;
for(int i=1; i<=m; i++){
    int a, b, c, p;
    cin>>a>>b>>c>>p;
    g[a].pb({b, {c, p} });
    g[b].pb({a, {c, p} });
}



for(int i=1; i<=n; i++){
    sort(g[i].begin(), g[i].end());
    if(g[i].empty()){
        continue;
    }
    int ac=g[i][0].sc.ft, sum=0;
    for(int j=0; j<g[i].size(); j++){
        if(ac!=g[i][j].sc.ft){
            csum[mp(i, ac) ]=sum;
            sum=0;
            ac=g[i][j].sc.ft;
        }
        sum+=g[i][j].sc.sc;
    }
    csum[mp(i, ac) ]=sum;
}






cout<<dijkstra();


return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:127:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int j=0; j<g[i].size(); j++){
      |                  ~^~~~~~~~~~~~

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