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/
↵
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/