Algorytm Prima-Dijkstry

/**
  *   Autor: Rafał Nowak
  *   Data : 2008.02.27
  *   
  *   W pracy tej zaimplementowana algorytm Prima-Dijkstry znajdowania minimalnego
  *   drzewa spinajacego (MST).
  *   
  *   Dany: nieskierowany graf G z wagami na krawędziach
  *   
 
Przykładowe wejście:
6 10
1 2 2
1 6 1
1 5 3
4 1 5
2 6 2
2 3 5
4 3 4
3 5 4
4 5 4
5 6 3
 
  **/
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
 
const int infty = 1000000000; // uwaga na limit
int n,m;
vector< vector< pair<int,int> > > adj;
 
vector<bool> vis;
vector<int> waga, pi;
 
struct cmp
{
	// czy a jest mniejsze od b
	bool operator() (const int &a, const int &b)
	{
		if (waga[a] < waga[b]) return true;
		if (waga[a] > waga[b]) return false;
		return a<b;
	}
};
 
set<int, cmp> kopiec; // ;-)
 
void prim_dijkstra(int s)
{
	int v, u, c;
	waga.clear(); waga.resize(n, infty); 
	vis.clear(); vis.resize(n,false);
	pi.resize(n);
 
	waga[s] = 0; pi[s]=s; 
	kopiec.clear(); for (int i=0; i<n; i++) kopiec.insert(i);
 
	// MST to drzewo zawierające wierzchołki, których nie w zbiorze kopiec,
	// czyli na razie jest ono pustym drzewem.
 
	while( !kopiec.empty() )
	{
		u = *(kopiec.begin()); // weź wierzchołek najbliżej drzewa MST
		kopiec.erase(kopiec.begin());
		vis[u]=true; // dodajemy wierzchołek v do drzewa MST
		// a dodał go wierzchołek pi[u]
 
		for (int i=0; i<adj[u].size(); i++)
		{
			v = adj[u][i].first;
			if (!vis[v])
			{
				c = adj[u][i].second;
				if (c < waga[v]) // w alg. Dijkstry jest tutaj waga[u]+c < waga[v]
				{
					// uaktualniamy wagę wierzchołka v
					kopiec.erase(kopiec.find(v));
					waga[v] = c; // w alg. Dijkstry jest tutaj waga[v]=waga[u]+c;
					kopiec.insert(v);
					pi[v] = u;
				}
			}
		}
	}
}
 
int main(void)
{
	int a,b,c;
 
	scanf("%d %d", &n, &m);
	adj.resize(n);
	for (int i=0; i<m; i++)
	{
		scanf("%d %d %d", &a, &b, &c); // c = koszt krawędzi od a do b
		a--; b--;
		adj[a].push_back( make_pair(b,c) );
		adj[b].push_back( make_pair(a,c) );
	}
 
	prim_dijkstra(0); // zaczynamy algorytm w wierzchołku nr 0
 
	// alg. Dijkstry wypełni całą tablicę pi[..] krawędziami drzewa MST
	// suma wag waga[..], daje wagę całego drzewa MST
 
	int suma = 0; for (int i=1; i<n; i++) suma += waga[i]; // uwaga, bo waga[0]=0
 
	printf("Koszt minimalnego drzewa spinającego wynosi %d\n", suma);
	printf("Drzewo złożone jest z następujących krawędzi:\n");
	for (int i=1; i<n; i++) // specjalnie pomijam wierzhołek nr 0
		// zwiekszam numery, bo zakładam, że na wejściu wierzchołki numerowane są od 1
		printf("%d -- %d\n", i+1, pi[i]+1); 
	return 0;
}