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;
}