Обратная задача SSSP (inverse-SSSP - обратная задача кратчайших путей из одной вершины)

Имеется взвешенный неориентированный мультиграф G из N вершин и M рёбер. Дан массив P[1..N] и указана некоторая начальная вершина S. Требуется изменить веса рёбер так, чтобы для всех I P[I] было равно длине кратчайшего пути из S в I, причём сумма всех изменений (сумма модулей изменений весов рёбер) была бы наименьшей. Если этого сделать невозможно, то алгоритм должен выдать "No solution". Делать вес ребра отрицательным запрещено.

Описание решения

Мы решим эту задачу за линейное время, просто перебрав все рёбра (т.е. за один проход).

Пусть на текущем шаге мы рассматриваем ребро из вершины A в вершину B длиной R. Мы предполагаем, что для вершины A уже все условия выполнены (т.е. расстояние от S до A действительно равно P[A]), и будем проверять выполнение условий для вершины B. Имеем несколько вариантов ситуации:

1. P[A] + R < P[B]
Это означает, что мы нашли путь, более короткий, чем он должен быть. Поскольку P[A] и P[B] мы изменять не можем, то мы обязаны удлинить текущее ребро (независимо от остальных рёбер), а именно выполнить:
R += P[B] - P[A] - R.
Кроме того, это означает, что мы нашли уже путь в вершину B из S, длина которого равна требуемому значению P[B], поэтому на последующих шагах нам не придётся укорачивать какие-либо рёбра (см. вариант 2).
2. P[A] + R >= P[B]
Это означает, что мы нашли путь, более длинный, чем требуемый. Поскольку таких путей может быть несколько, мы должны выбрать среди всех таких путей (рёбер) то, которое потребует наименьшего изменения. Повторимся, что если мы удлиняли какое-то ребро, ведущее в вершину B (вариант 1), то этим мы фактически построили кратчайший путь в вершину B, а потому укорачивать никакое ребро уже не надо будет. Таким образом, для каждой вершины мы должны хранить ребро, которое собираемся укорачивать, т.е. ребро с наименьшим весом изменения.

Таким образом, просто перебрав все рёбра, и рассмотрев для каждого ребра ситуацию (за O(1)), мы решим обратную задачу SSSP за линейное время.

Если в какой-то момент мы пытаемся изменить уже изменённое ребро, то, очевидно, этого делать нельзя, и следует выдать "No solution". Кроме того, у некоторых вершин может быть так и не достигнута требуемая оценка кратчайшего пути, тогда ответ тоже будет "No solution". Во всех остальных случаях (кроме, конечно, явно некорректных значений в массиве P, т.е. P[S] != 0 или отрицательные значения) ответ будет существовать.

Реализация

Программа выводит "No solution", если решения нет, иначе выводит в первой строке минимальную сумму изменений весов рёбер, а в последующих M строках - новые веса рёбер.

const int INF = 1000*1000*1000;
int n, m;
vector<int> p (n);

bool ok = true;
vector<int> cost (m), cost_ch (m), decrease (n, INF), decrease_id (n, -1);
decrease[0] = 0;
for (int i=0; i<m; ++i) {
	int a, b, c; // текущее ребро (a,b) с ценой c
	cost[i] = c;

	for (int j=0; j<=1; ++j) {
		int diff = p[b] - p[a] - c;
		if (diff > 0) {
			ok &= cost_ch[i] == 0 || cost_ch[i] == diff;
			cost_ch[i] = diff;
			decrease[b] = 0;
		}
		else
			if (-diff <= c && -diff < decrease[b]) {
				decrease[b] = -diff;
				decrease_id[b] = i;
			}
		swap (a, b);
	}
}

for (int i=0; i<n; ++i) {
	ok &= decrease[i] != INF;
	int r_id = decrease_id[i];
	if (r_id != -1) {
		ok &= cost_ch[r_id] == 0 || cost_ch[r_id] == -decrease[i];
		cost_ch[r_id] = -decrease[i];
	}
}

if (!ok)
	cout << "No solution";
else {
	long long sum = 0;
	for (int i=0; i<m; ++i)  sum += abs (cost_ch[i]);
	cout << sum << '\n';
	for (int i=0; i<m; ++i)
		printf ("%d ", cost[i] + cost_ch[i]);
}