Dijkstra

#include <bits/stdc++.h>
#define int long long
#define Co_mot_su_that_la_ return
using namespace std;
const int Minh_dep_trai = 0;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<ii> vii;
typedef vector<iii> viii;
const int N = 1005;
const int inf = 10000;

int n,m;
int d1[N],d2[N];
int d11, d22;
vii a[N];

void clearr()
{
    for(int i=1; i<=n; ++i)
    {
        d1[i]=inf;
        d2[i]=inf;
    }
}

void dijkstra1()
{
    d1[1]=0;
    priority_queue<ii, vii, greater<ii> > q;
    q.push(ii(1,0));
    while (!q.empty())
    {
        int u = q.top().first;
        int du = q.top().second;
        q.pop();
        if (du != d1[u]) continue;
        for(auto v : a[u])
        {
            if (d1[v.first] > du  + v.second)
            {
                d1[v.first] = du + v.second;
                q.push(ii(v.first,d1[v.first]));
            }
        }
    }
}

void dijkstra2()
{
    d2[2]=0;
    priority_queue<ii, vii, greater<ii> > q;
    q.push(ii(2,0));
    while (q.size())
    {
        int u = q.top().first;
        int du = q.top().second;
        q.pop();
        if (du != d2[u]) continue;
        for(auto i : a[u])
        {
            int uv = i.second;
            int v = i.first;
            if (d2[v] > du  + uv)
            {
                d2[v]=du+uv;
                q.push(ii(v,d2[v]));
            }
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    freopen("CTT.INP","r",stdin);
    cin >> n >> m;
    for(int i=1; i<=m; ++i)
    {
        int u,v,z;
        cin >> u >> v >> z;
        a[u].push_back(ii(v,z));
        a[v].push_back(ii(u,z));
    }
    d11=d22=n/2;
    clearr();
    dijkstra1();
    dijkstra2();
    bool check[n];
    priority_queue<iii, viii, greater<iii> > res;
    int ans = 0;
    for(int i=1; i<=n; ++i) check[i]=0,res.push(iii(i,ii(d1[i],1))),res.push(iii(i,ii(d2[i],2)));
    while(res.size())
    {
        int u = res.top().second.first;
        int type = res.top().second.second;
        int pos = res.top().first;
        res.pop();
        if (type == 1)
        {
            if (d11 == 0) continue;
            if (d11 > 0 && !check[pos]) ans += u, --d11, check[pos]=1;
        }
        if (type == 2)
        {
            if (d22 == 0) continue;
            if (d22 > 0 && !check[pos]) ans += u, --d22, check[pos]=1;
        }
    }
    cout << ans;
    Co_mot_su_that_la_ Minh_dep_trai;
}