Quase menor caminho

quase_menor.cpp

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> ii;

const int inf = 0x3f3f3f3f;
const int maxn = 510;

vector<ii> v[maxn];
vector<ii> mir[maxn];
vector<ii> inv[maxn];

int d[maxn];
int vis[maxn];

void dijkstra(int ini)
{
	memset(d, 0x3f, maxn*4);
	d[ini] = 0;

	for (int i = 0; i < maxn; i++) mir[i].clear();

	priority_queue<ii, vector<ii>, greater<ii> > pq;

	pq.push({0, ini});

	while (!pq.empty()) {

		int w, at;
		tie(w, at) = pq.top();
		pq.pop();

		if (w > d[at]) continue;
		
		for (ii uu : v[at]) {

			int u = uu.ff, ww = uu.ss;

			if (d[u] == w + ww) {

				mir[u].push_back({at, ww});
			}
			else if (d[u] > w + ww) {

				mir[u].clear();
				d[u] = w + ww;
				mir[u].push_back({at, ww});

				pq.push({d[u], u});
			}
		}
	}
}

void dfs(int x)
{
	vis[x] = 1;

	for (ii uu : mir[x]) {

		int u = uu.ff, w = uu.ss;

		inv[u].push_back({x, w});

		if (vis[u]) continue;

		dfs(u);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	while (true) {

		int n, m;
		cin >> n >> m;

		if (n == 0 and m == 0) break;

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

			mir[i].clear();
			inv[i].clear();
			v[i].clear();
			vis[i] = 0;
		}

		int ini, fim;
		cin >> ini >> fim;

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

			int a, b, w;
			cin >> a >> b >> w;

			v[a].push_back({b, w});
		}

		dijkstra(ini);

		dfs(fim);

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

			sort(v[i].begin(), v[i].end());
			sort(inv[i].begin(), inv[i].end());

			vector<ii> r;

			set_difference(v[i].begin(), v[i].end(), inv[i].begin(), inv[i].end(),
				           back_inserter(r));

			v[i] = r;
		}

		dijkstra(ini);

		if (d[fim] == inf) cout << -1 << "\n";
		else cout << d[fim] << "\n";
	}
}