#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();
}
}
You need to upgrade your WHILE cycle.
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.use visited array to ensure not visit same node again which is already minimum.