Алгоритм Дейкстры на поиск минимального пути в графе. Копирайт ставить, если сам делал?)))
Code
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
const int NMAX = 2001;
const int MMAX = 200001;
int heap[MMAX];
int TT = 0;
int d[NMAX];
int mas[NMAX][NMAX];
int n, m, f, s;
bool Empty()
{
return (TT == 0);
}
int Min(int i, int j)
{
if (i < j) return i;
else return j;
}
void Init()
{
for (int i = 1; i <= NMAX; i++)
for (int j = 1; j <= NMAX; j++)
mas[i][j] = 0;
}
void ReadData()
{
int _a, _b, _v;
scanf("%d%d%d%d", &n, &m, &s, &f);
for (int i = 0; i < m; i++)
{
scanf("%d %d %d", &_a, &_b, &_v);
mas[_a][_b] = mas[_b][_a] = _v;
}
}
void Swap(int i1, int i2)
{
int tmp = heap[i1];
heap[i1] = heap[i2];
heap[i2] = tmp;
}
void Insert(int x)
{
int index = TT;
TT++;
heap[index] = x;
while (index > 0)
{
int parent = (index - 1)/2;
if (heap[parent] <= heap[index])
break;
Swap(parent, index);
index = parent;
}
}
int Min()
{
TT--;
int temp = heap[TT];
heap[TT] = heap[0];
heap[0] = temp;
int i = 0;
while (i * 2 + 1 < TT)
{
int childA = i * 2 + 1;
int childB = i * 2 + 2;
if (childB >= TT)
childB = childA;
int childMin = 0;
if (heap[childB] < heap[childA])
childMin = childB;
else childMin = childA;
if (heap[i] <= heap[childMin])
break;
Swap(childMin, i);
i = childMin;
}
return heap[TT];
}
void Djkstra(int start, int n)
{
for (int i = 1; i <= n; i++)
d[i] = INT_MAX;
d[start] = 0;
Insert(start);
while (!Empty())
{
int v = Min();
for (int w = 1; w <= n; w++)
{
if (mas[v][w] == 0)
continue;
if (d[v] + mas[v][w] < d[w])
{
d[w] = d[v] + mas[v][w];
Insert(w);
}
}
}
}
int main()
{
Init();
ReadData();
Djkstra(s, n);
printf("%d", d[f]);
return 0;
}