Shortest route 1 | CSES

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

https://cses.fi/problemset/task/1671/

This is the task and at the first look its obvious that its a standard dijkstra problem, But due to some reason my code is giving TLE for 2 large test cases which I am sure the standard dijkstra code should be able to handle. Can someone take a look at this and provide some insight.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
 
bool inside(ll i, ll j, ll r, ll c)
{
  return (i < r && j < c && i >= 0 && j >= 0);
}
 
pair<ll, ll> directions[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 
 
void solve()
{
  ll n ; 
  cin>>n;
 
  ll m ;
  cin>>m ;
 
  vector<pair<ll , ll >>adj[n+1];
 
 
  for(ll i = 0  ; i< m ; i++)
  {
    ll a, b , c ;
    cin>>a>>b>>c ;
 
    adj[a].push_back({b ,c});
    // adj[b].push_back({a,c});
 
  }
 
  vector<ll> dist(n + 1, LLONG_MAX);
  // vector<bool>vis(n+1, false);
 
  priority_queue<pair<ll ,ll >  , vector<pair< ll , ll > >  , greater<pair<ll ,ll >> > q ;
 
  q.push({0 , 1});
  dist[1] = 0 ;
 
  while(q.empty()==false)
  {
    auto u = q.top();
    q.pop();
 
    for(auto x:  adj[u.second])
    {
      // cout<<dist[x[0]]<<" "<<dist[u.first]<<" "<<x[1]<<endl;
 
        if(dist[x.first] > dist[u.second] + x.second)
        {
          dist[x.first] = dist[u.second] + x.second;
          q.push({dist[x.first], x.first});
        }
    }
  }
 
  for(ll i =1 ; i<=n  ; i++)
  cout<<dist[i]<<" ";
  cout<<endl;
 
} 
 
 
 
int main()
{
 
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
 
  ull t = 1;
  // cin >> t;
  // cout << "nooml";
  while (t--)
  {
    solve();
  }
}

Failing TCs : https://cses.fi/file/6202e05529aba02706fe1c03ec7d07ed68c2e254b69047129b52185f875b9a1e/1/1/ https://cses.fi/file/a563cff68cf3d8ade012345cf49bc668cdb1f02f7a75317091066f81c0db16d5/1/1/

Comments (2)

Show archived | Write comment?

not.derwes.at.all

2 years ago, # |

← Rev. 5 →

You need to upgrade your WHILE cycle.

...
   auto u = q.top();
   q.pop();
    int curDist = u.first;
    if(curDist > dist[u.second]) {
        continue;
    }
...

without this IF your asymptotic can expand up to O(nm). Because you can add several identical pairs with the same vertex but different weights, but we need to take only the best pair.

If you have 2 pair like this: {D1, V} and {D2, V}. When you relax first pair all the relaxations with the second pair are useless if D1 < D2.

→ Reply

GOURAB

23 months ago, # |

use visited array to ensure not visit same node again which is already minimum.

mkmeden's blog