It gives Tle, but Sets doesn't

[ParagSaini]

I tried this algorithm on problem : https://cses.fi/problemset/task/1671/ It gives TLE with this code, but when i did using the sets and erasing the useless nodes, it got accepted. TLE CODE:

include<bits/stdc++.h>

using namespace std; typedef long long ll; typedef pair<ll, ll> p32; const ll mod = 1000000007; vector<vector<pair<ll, ll>>> edges; ll n, m;

void dijsktra() { priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;// min-heap ; In pair => (dist,from) vector distTo(n+1,LLONG_MAX); // 1-indexed array for calculating shortest paths;

distTo[1] = 0;
pq.push(make_pair(0,1));    // (dist,from)

while( !pq.empty() ){
    ll dist = pq.top().first;
    ll prev = pq.top().second;
    pq.pop();

    vector<pair<ll,ll> >::iterator it;
    for( auto it : edges[prev]){
        ll next = it.first;
        ll nextDist = it.second;
        if( distTo[next] > distTo[prev] + nextDist){
            distTo[next] = distTo[prev] + nextDist;
            pq.push(make_pair(distTo[next], next));
        }
    }

}

for(int i = 1 ; i<=n ; i++) cout << distTo[i] << " ";
cout << "\n";

} void solve() { cin>>n>>m; edges.resize(n+1); for(ll i=0; i<m; i++) { ll s, d, w; scanf("%lld %lld %lld", &s, &d, &w); edges[s].push_back(make_pair(d, w)); } dijsktra(); }

void init_code() {

ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

} int main() {

init_code();

ll t;
t = 1;
while(t--) {
    solve();
}
return 0;

}

Accepted CODE using SETS:

include<bits/stdc++.h>

using namespace std; typedef long long ll; typedef pair<ll, ll> p32; const ll mod = 1000000007; vector<vector<pair<ll, ll>>> edges; ll n, m;

void dijsktra() { set<pair<ll, ll>> setds; // for getting node in ascending order of their weight till now. vector dist(n+1, LLONG_MAX);

dist[1] = 0;     // starting from node 1.
setds.insert(make_pair(0, 1));

while(!setds.empty()) {
    pair<ll, ll> minWeightNode = (*setds.begin());

    for(auto child : edges[minWeightNode.second]) {
        ll node = child.first;
        ll w = child.second;
        ll tillDist = minWeightNode.first + w;

        if(tillDist < dist[node]) {
            if(dist[node] != LLONG_MAX) {
                setds.erase(make_pair(dist[node], node));
            }
            dist[node] = tillDist;   
            setds.insert(make_pair(tillDist, node));
        }
    }
    setds.erase((*setds.begin()));
}

for(ll i=1; i<=n; i++) printf("%lld ", dist[i]);

} void solve() { cin>>n>>m; edges.resize(n+1); for(ll i=0; i<m; i++) { ll s, d, w; scanf("%lld %lld %lld", &s, &d, &w); edges[s].push_back(make_pair(d, w)); } dijsktra(); }

void init_code() {

ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

} int main() {

init_code();

ll t;
// cin>>t;
t = 1;
while(t--) {
    solve();
}
return 0;

}

[striver79]

Cses time limit is just too strict. However both methods are correct..

On Sat, 26 Jun 2021 at 6:07 PM, Parag Saini @.***> wrote:

I tried this algorithm on problem : https://cses.fi/problemset/task/1671/ It gives TLE with this code, but when i did using the sets and erasing the useless nodes, it got accepted. TLE CODE:

include<bits/stdc++.h>

using namespace std; typedef long long ll; typedef pair<ll, ll> p32; const ll mod = 1000000007; vector<vector<pair<ll, ll>>> edges; ll n, m;

void dijsktra() { priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;// min-heap ; In pair => (dist,from) vector distTo(n+1,LLONG_MAX); // 1-indexed array for calculating shortest paths;

distTo[1] = 0; pq.push(make_pair(0,1)); // (dist,from)

while( !pq.empty() ){ ll dist = pq.top().first; ll prev = pq.top().second; pq.pop();

vector<pair<ll,ll> >::iterator it; for( auto it : edges[prev]){ ll next = it.first; ll nextDist = it.second; if( distTo[next] > distTo[prev] + nextDist){ distTo[next] = distTo[prev] + nextDist; pq.push(make_pair(distTo[next], next)); } }

}

for(int i = 1 ; i<=n ; i++) cout << distTo[i] << " "; cout << "\n";

} void solve() { cin>>n>>m; edges.resize(n+1); for(ll i=0; i<m; i++) { ll s, d, w; scanf("%lld %lld %lld", &s, &d, &w); edges[s].push_back(make_pair(d, w)); } dijsktra(); }

void init_code() {

ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

endif

} int main() {

init_code();

ll t; t = 1; while(t--) { solve(); } return 0;

}

Accepted CODE using SETS:

include<bits/stdc++.h>

using namespace std; typedef long long ll; typedef pair<ll, ll> p32; const ll mod = 1000000007; vector<vector<pair<ll, ll>>> edges; ll n, m;

void dijsktra() { set<pair<ll, ll>> setds; // for getting node in ascending order of their weight till now. vector dist(n+1, LLONG_MAX);

dist[1] = 0; // starting from node 1. setds.insert(make_pair(0, 1));

while(!setds.empty()) { pair<ll, ll> minWeightNode = (*setds.begin());

for(auto child : edges[minWeightNode.second]) { ll node = child.first; ll w = child.second; ll tillDist = minWeightNode.first + w;

  if(tillDist < dist[node]) {
      if(dist[node] != LLONG_MAX) {
          setds.erase(make_pair(dist[node], node));
      }
      dist[node] = tillDist;  
      setds.insert(make_pair(tillDist, node));
  }

} setds.erase((*setds.begin())); }

for(ll i=1; i<=n; i++) printf("%lld ", dist[i]);

} void solve() { cin>>n>>m; edges.resize(n+1); for(ll i=0; i<m; i++) { ll s, d, w; scanf("%lld %lld %lld", &s, &d, &w); edges[s].push_back(make_pair(d, w)); } dijsktra(); }

void init_code() {

ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

endif

} int main() {

init_code();

ll t; // cin>>t; t = 1; while(t--) { solve(); } return 0;

}

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/striver79/StriversGraphSeries/issues/11, or unsubscribe https://github.com/notifications/unsubscribe-auth/ALIBT4T7GWALZ7AWHMVBK2DTUXCYLANCNFSM47LKCOHQ .

-- Regards, Raj(Striver) GodSpeed!!

[ParagSaini]

Isn't using sets is better than priority_queues? what should I use sets or priority_queue?

[Pankaj1417]

using sets is a better option than to use priority queue