HIWAY - Hai đường đi

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<climits>
#include<queue>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;

typedef pair<int, int> ii;
#define N 100
int c[N][N], d[N], t[N], n, m, s, f;

void enter() {
	scanf("%d%d%d%d",&n,&m,&s,&f);
	--s; --f;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			c[i][j] = INT_MAX;
	for(int i = 0; i < m; ++i) {
		int u, v, l; scanf("%d%d%d",&u,&v,&l);
		--u; --v; c[u][v] = c[v][u] = l;
	}
}

int Dijkstra() {
	priority_queue<ii, vector<ii>, greater<ii> > qu;
	fill(d, d+n, INT_MAX); d[s] = 0; t[s] = -1;
	qu.push(ii(0, s));
	while(!qu.empty()) {
		int du = qu.top().first, u = qu.top().second; qu.pop();
		if(du > d[u]) continue;
		for(int v = 0; v < n; ++v)
			if(c[u][v] != INT_MAX && du + c[u][v] < d[v]) {
				qu.push(ii(d[v] = du + c[u][v], v));
				t[v] = u;
			}
	}
	for(int v = f; t[v] != -1; v = t[v]) {
		c[v][t[v]] = -c[v][t[v]];
		c[t[v]][v] = INT_MAX;
	}
	return d[f];
}

int FordBellman() {
	fill(d, d+n, INT_MAX); d[s] = 0; t[s] = -1;
	for(int step = 0, stop = 0; step < n-1 && !stop; ++step) {
		stop = 1;
		for(int u = 0; u < n; ++u) if(d[u] != INT_MAX)
			for(int v = 0; v < n; ++v) if(c[u][v] != INT_MAX && d[u] + c[u][v] < d[v]) {
				d[v] = d[u] + c[u][v];
				t[v] = u;
				stop = 0;
			}
	}
	for(int v = f; t[v] != -1; v = t[v]) c[t[v]][v] = INT_MAX; 
	return d[f];
}

void EditGraph() {
	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
			if(c[i][j] != INT_MAX && c[j][i] != INT_MAX)
				c[i][j] = c[j][i] = INT_MAX;
}

stack<int> st;
void dfs(int u) {
	if(u == s) {
		printf("%d %d", st.size() + 1, s+1);
		for(; !st.empty(); st.pop()) printf(" %d", st.top()+1);
		printf("\n");
	} else
		for(int v = 0; v < n; ++v)
			if(c[u][v] != INT_MAX) {
				st.push(u);
				dfs(v);
			}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	enter();
	printf("%d\n", Dijkstra() + FordBellman());
	EditGraph();
	dfs(f);
	return 0;
}

Download