FLOYD - Floyd hoặc Dijkstra ( Cơ bản )
Tác giả: ladpro98
Ngôn ngữ: C++
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 101;
const int oo = 1000000009;
using namespace std;
int a[N][N], T[N][N];
int n, m, Q;
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> Q;
REP(i, 1, n) REP(j, 1, n)
if (i != j) a[i][j] = oo;
REP(i, 1, n) T[i][i] = i;
int u, v, c, kind;
FOR(i, 0, m) {
cin >> u >> v >> c;
a[u][v] = a[v][u] = c;
T[u][v] = v; T[v][u] = u;
}
REP(k, 1, n) REP(i, 1, n) REP(j, 1, n)
if (a[i][j] > a[i][k] + a[k][j]) {
a[i][j] = a[i][k] + a[k][j];
T[i][j] = T[i][k];
}
while (Q--) {
cin >> kind >> u >> v;
if (kind == 0) cout << (a[u][v] >= oo ? -1 : a[u][v]) << '\n';
else {
if (u == v) {
cout << "2 " << u << ' ' << v << '\n';
continue;
}
VI path;
while (u != v) {
path.PB(u);
u = T[u][v];
}
cout << SZ(path) + 1 << ' ';
TR(it, path) cout << *it << ' '; cout << v;
cout << '\n';
}
}
return 0;
}