Пространства имён
Варианты
Действия

Обсуждение:Заглавная страница

Материал из cppreference.com

[править] Расширенный алгоритм Евклида

int gcd (int a, int b, int & x, int & y) {
	if (a == 0) {
		x = 0; y = 1;
		return b;
	}
	int x1, y1;	
	int d = gcd (b%a, a, x1, y1);	
	x = y1 - (b / a) * x1;
	y = x1;	
	return d;

}

[править] Бинарное возведение в степень

int binpow (int a, int n) {
	int res = 1;
	while (n) {
		if (n & 1)
			res *= a;
		a *= a;
		n >>= 1;
	}
	return res;
}

[править] Алгоритм Дейкстры для поиска кратчайших путей

const int INF = 1000000000;
 
int main() {
	int n;
	... reading n ...
	vector < vector < pair<int,int> > > g (n);
	... reading graph ...
	int s = ...; // стартовая вершина
 
	vector<int> d (n, INF),  p (n);
	d[s] = 0;
	vector<char> u (n);
	for (int i=0; i<n; ++i) {
		int v = -1;
		for (int j=0; j<n; ++j)
			if (!u[j] && (v == -1 || d[j] < d[v]))
				v = j;
		if (d[v] == INF)
			break;
		u[v] = true;
 
		for (size_t j=0; j<g[v].size(); ++j) {
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]) {
				d[to] = d[v] + len;
				p[to] = v;
			}
		}
	}
}

Восстановление пути

vector<int> path;
for (int v=t; v!=s; v=p[v])
	path.push_back (v);
path.push_back (s);
reverse (path.begin(), path.end());