[Algorithm] Prim !

I have recieved emails about bugs of my codes in other blog about Python
This page actually is just the page that I save all my codes. If anyone interesting, you can use codes here.
For tutorials, just browse my other blog. This one is about Prim algorithm:


#include <iostream>
#include <queue>
#include <vector>
#define MAXN 100005 // num of vertexs
#define INFTY 1000000000

using namespace std;
// minimum spanning tree

vector< pair<int,int> > adj[MAXN];//if having many testcases, you should declara adj in procedure main()
priority_queue< pair<int,int> > pq;
int key[MAXN];
int parent[MAXN];
int vis[MAXN];

int main () {
    int N, M, sumTree=0; // N is num of vertexs, M is num of edges
    // vertex is indexed from 0 to N-1
    cin >> N >> M ;
    for (int i = 0; i<M; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        adj[a].push_back (make_pair (b,l));
        adj[b].push_back (make_pair (a,l));
    }

    for (int i = 0; i<N; i++) {
        key[i] = INFTY;
        vis[i] = 0;
    }
     
    key[0] = 0;
    parent[0] = -1;
    pq.push (make_pair (-0,0)); // minus sign to convert largest num to smallest num
    while (!pq.empty ()) {
        int v = pq.top ().second;
        pq.pop ();
        if (vis[v]) continue;
        sumTree += key[v];
        vis[v] = 1;
        for (int i = 0; i<adj[v].size (); i++) {
            if (adj[v][i].second < key[adj[v][i].first] && !vis[adj[v][i].first]) {
                key[adj[v][i].first] = adj[v][i].second;
                parent[adj[v][i].first] = v;
                pq.push (make_pair (-key[adj[v][i].first], adj[v][i].first));
            }
        }
    }
    //print
    cout << sumTree << endl;
    return 0;
}

[Algorithm] Dijkstra !

Today, one of my friends asks me about Dijkstra ! Computer Science students are familiar with this algorithm. But maybe, beginners will have difficulty in coding and using datastructure.

Below is my code. Hope it will help my friend and beginners. I use C++ in the code: 

#include <iostream>

#include <queue>

#include <vector>

 

#define MAXN 50005 // num of vertexs

#define INFTY 1000000000

using namespace std;

// minimum distance from vertex u  to the others

vector< pair<int,int> > adj[MAXN];//if having many testcases, you should declara adj in procedure main()

priority_queue< pair<int,int> > pq;

int dist[MAXN];

int vis[MAXN];

int parent[MAXN];

int main () {

    int N, M, u; // N is num of vertexs, M is num of edges, u is first vertex, dist[u]=0;     

    // vertex is indexed from 0 to N-1

    cin >> N >> M >> u;

    for (int i = 0; i<M; i++) {

        int a, b, l;

        cin >> a >> b >> l;

        adj[a].push_back (make_pair (b,l));

        adj[b].push_back (make_pair (a,l));

    }

    for (int i = 0; i<N; i++) {

        dist[i] = INFTY;

        vis[i] = 0;

    }

    

    dist[u] = 0;

    parent[u] = -1;

    pq.push (make_pair (-0,u)); // minus sign to convert largest num to smallest num

    while (!pq.empty ()) {

        int v = pq.top ().second;

        pq.pop ();

        if (vis[v]) continue;

        vis[v] = 1;

        for (int i = 0; i<adj[v].size (); i++) {

            if (dist[v] + adj[v][i].second < dist[adj[v][i].first] && !vis[adj[v][i].first]) {

                dist[adj[v][i].first] = dist[v] + adj[v][i].second;

                parent[adj[v][i].first] = v;

                pq.push (make_pair (-dist[adj[v][i].first],adj[v][i].first));

            }

        }

    }    

    //print dist[]

    for(int i=0 ; i<N ; i++) cout << dist[i] << endl;    

    return 0;

}