dijkstra, C++ (gcc)

dijkstra

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;++i)
    {
        int n,m;
        cin>>n>>m;
        vector<vector<pair<int,int>>>gr(n+1);
        for(int i=0;i<m;++i)
        {
            int u,v,w;
            cin>>u>>v>>w;
            gr[u].pb(mp(v,w));
        }
        int aa,bb;
        cin>>aa>>bb;
        ll dis[n]={0};
        map<pair<ll,ll>,ll>ma;
        for(int i=0;i<=n;++i)
            dis[i]=1e18;
        dis[aa]=0;
        for(int i=1;i<=n;++i)
            ma[mp(dis[i],i)]=1;
        while(ma.size()>0)
        {
            ll d1=ma.begin()->first.first;
            ll d2=ma.begin()->first.second;
            if(d1==1e18)
                break;
            ma.erase(mp(d1,d2));
            for(int i=0;i<gr[d2].size();++i)
            {
                ll r=gr[d2][i].first;
                if(dis[r]>dis[d2]+gr[d2][i].second)
                {
                    ma.erase(mp(dis[r],r));
                    dis[r]=dis[d2]+gr[d2][i].second;
                    ma[mp(dis[r],r)]=1;
                }
            }
        }
        if(dis[bb]==1e18)
            cout<<"NO"<<endl;
        else
            cout<<dis[bb]<<endl;
    }
}


run \| edit \| history \| help	0