Shortest route 1 | CSES

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

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

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

mkmeden's blog