Shortest route 1 | CSES 
Difference between en1 and en2, changed 3 character(s)
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.↵

<spoiler summary="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();↵
  }↵
}↵

```↵
</spoiler>↵

 ↵


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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English mkmeden 2022-08-12 18:28:30 3 (published)
en1 English mkmeden 2022-08-12 18:25:35 2012 Initial revision (saved to drafts)