## Editorial for Floyd hoặc Dijkstra (Cơ bản)

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

uses math;
const fi='';
oo=100000000;
var m,n,k,num,s,t:longint;
a,tr:array[1..100,1..100] of longint;
re:array[1..100] of longint;

procedure rf;
var i,x,y,c:longint;
begin
for x:=1 to n-1 do
for y:=x+1 to n do
begin
a[x,y]:=oo;
tr[x,y]:=y;
a[y,x]:=oo;
tr[y,x]:=x;
end;
for x:=1 to n do tr[x,x]:=x;
for i:=1 to m do
begin
a[x,y]:=min(a[x,y],c);
a[y,x]:=min(a[y,x],c);
end;
end;

procedure pr;
var i,j,k:longint;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,k]+a[k,j] then
begin
a[i,j]:=a[i,k]+a[k,j];
tr[i,j]:=tr[i,k];
end;
end;

procedure wf;
var i,j,z:longint;
begin
for i:=1 to k do
begin
if z=0 then writeln(a[s,t])
else
begin
num:=1; re[1]:=s;
repeat
s:=tr[s,t];
inc(num);
re[num]:=s;
until t=s;
write(num);
for j:=1 to num do write(' ',re[j]);
writeln;
end;
end;
end;

begin
assign(input,fi); reset(input);
rf;
pr;
wf;
close(input);
end.


#### Code mẫu của happyboy99x

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

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#define TR(v, it) for(typeof((v).begin()) it = (v).begin(), _e = (v).end(); it != _e; ++it )
#define INF 1000000000

vvii g;
int t[105][105], d[105][105];
int n, m, k;

void dijkstra( vvii & g, int s, int d[], int t[] ) {
priority_queue<ii> q; q.push(ii(0, s));
for( int i = 0; i < n; ++i ) d[i] = INF;
d[s] = 0; t[s] = s;
while( !q.empty() ) {
int du = q.top().first, u = q.top().second; q.pop();
if (du > d[u]) continue;
TR(g[u], it) {
int v = it->first, l = it->second;
if (d[v] > du + l) {
d[v] = du + l; t[v] = u;
q.push(ii(d[v], v));
}
}
}
}

int main() {
scanf( "%d%d%d", &n, &m, &k );
g = vvii(n, vii());
while(m--) {
int u, v, l; scanf( "%d%d%d", &u, &v, &l );
g[--u].push_back(ii(--v, l));
g[v].push_back(ii(u, l));
}
for( int i = 0; i < n; ++i ) dijkstra(g, i, d[i], t[i]);
while(k--) {
int q, u, v; scanf( "%d%d%d", &q, &u, &v );
--u; --v;
if(q) {
stack<int> st; int x = v; st.push(x);
do {
x = t[u][x];
st.push(x);
} while( x != u );
printf( "%d", st.size() );
while(!st.empty()) {
printf( " %d", st.top()+1 );
st.pop();
}
printf("\n");
} else printf("%d\n", d[u][v]);
}
return 0;
}


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


#### Code mẫu của RR

{\$R+,Q+}
uses math;
const
FINP          =       '';
FOUT          =       '';
MAXN          =       111;

var
f1,f2         :       text;
n,m,k         :       longint;
c,trace       :       array[1..MAXN,1..MAXN] of longint;

procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;

procedure closeF;
begin
close(f1);
close(f2);
end;

procedure inp;
var
i,u,v:longint;
begin
for u:=1 to n do
for v:=1 to n do
c[u,v]:=1000111000;
for i:=1 to m do
begin
c[v,u]:=c[u,v];
end;
for i:=1 to n do c[i,i]:=0;
end;

procedure init;
var
i,j,k:longint;
begin
for i:=1 to n do
for j:=1 to n do
trace[i,j]:=j;

for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if c[i,j]>c[i,k]+c[k,j] then
begin
c[i,j]:=c[i,k]+c[k,j];
trace[i,j]:=trace[i,k];
end;
end;

procedure solve;
var
i,q,u,v,count:longint;
begin
for i:=1 to k do
begin
if q=0 then writeln(f2,c[u,v])
else
begin
count:=1; q:=u;
repeat
inc(count);
u:=trace[u,v];
until u=v;
write(f2,count,' ',q);
u:=q;
repeat
u:=trace[u,v];
write(f2,' ',u);
until u=v;
writeln(f2);
end;
end;
end;

begin
openF;
inp;
init;
solve;
closeF;
end.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define max 1000
#define maxEC 1000
#define maxC max*maxEC
long c[max][max],Trace[max][max],n,a,b,T,x;
//FILE *p;
void Enter()
{
//p=fopen("D:\\Hoc tap\\test\\FLOYD\\FLOYD.IN0","r");
long m,u,v;
scanf("%ld %ld %ld",&n,&m,&T);
for(long u=1;u<=n;u++)
for(long v=1;v<=n;v++)
{
if(u==v) c[u][v]=0;
else c[u][v]=maxC;
}
for(long i=1;i<=m;i++)
{
scanf("%ld %ld",&u,&v);
scanf("%ld",&c[u][v]);
c[v][u]=c[u][v];
}
}
void Floyd()
{
for(long u=1;u<=n;u++)
for(long v=1;v<=n;v++)
Trace[u][v]=v;
for(long k=1;k<=n;k++)
for(long u=1;u<=n;u++)
for(long v=1;v<=n;v++)
if(c[u][v]>c[u][k]+c[k][v])
{
c[u][v]=c[u][k]+c[k][v];
Trace[u][v]=Trace[u][k];
}
}
void Result()
{
for(long i=1;i<=T;i++)
{
scanf("%ld %ld %ld",&x,&a,&b);
if(c[a][b]==maxC)
printf("-1\n");
else
{
if(x==0) printf("%ld\n",c[a][b]);
else
{
long t=1;
long d=a;
do
{
d=Trace[d][b];
t++;
}while(d!=b);
printf("%ld ",t);
do
{
printf("%ld ",a);
a=Trace[a][b];
}while(a!=b);
printf("%ld\n",b);
}
}
}
}
main()
{
Enter();
Floyd();
Result();
//getch();
}


#### Code mẫu của ll931110

Program FLOYD;
Const
input  = '';
output = '';
Var
F,Trace: array[1..100,1..100] of longint;
n,m,k: longint;
val: array[1..100] of longint;
fi,fo: text;

Var
i,j,u,v: longint;
Begin
Assign(fi, input);
Reset(fi);

For i:= 1 to n do
For j:= 1 to n do if i = j then F[i,j]:= 0
else F[i,j]:= 10000000;

For i:= 1 to m do
Begin
F[v,u]:= F[u,v];
End;
End;

Procedure Floyd;
Var
k,u,v: longint;
Begin
For u:= 1 to n do
For v:= 1 to n do Trace[u,v]:= v;

For k:= 1 to n do
For u:= 1 to n do
For v:= 1 to n do
if F[u,v] > F[u,k] + F[k,v] then
Begin
F[u,v]:= F[u,k] + F[k,v];
Trace[u,v]:= Trace[u,k];
End;
End;

Procedure PrintResult;
Var
x,u,v,i,j,num: longint;
Begin
Assign(fo, output);
Rewrite(fo);
For i:= 1 to k do
Begin

If x = 0 then writeln(fo, F[u,v]);
If x = 1 then
Begin
num:= 0;

Repeat
inc(num);
val[num]:= u;
u:= Trace[u, v];
Until u = v;

inc(num);
Write(fo, num, ' ');

For j:= 1 to num - 1 do write(fo, val[j], ' ');
Writeln(fo, v);
End;
End;
Close(fo);
Close(fi);
End;

Begin
Floyd;
PrintResult;
End.


#### Code mẫu của skyvn97

const     INP        =        '' ;
OUT        =        '' ;

maxn       =        100      ;
maxc       =        10000000 ;

var       n , m , cau_hoi :  integer ;
a          :       array[1..maxn,1..maxn] of longint ;
trace      :       array[1..maxn,1..maxn] of byte    ;
fi , fo    :       text    ;

var
i , j , u , v , pt , loai : integer ;
l : array[1..maxn] of integer ;

procedure truy_vet( u , v : integer ) ;
var
k : integer ;
begin
k := trace[u,v] ;
if k = 0 then begin
inc( pt )  ;
l[pt] := v ;
exit ;
end ;
truy_vet( u , k ) ;
truy_vet( k , v ) ;
end ;

begin
for i := 1 to cau_hoi do begin
read( fi , loai , u , v ) ;
if loai = 0 then writeln( fo , a[u,v] ) { cau hoi loai 0 }
else
{ cau hoi loai 1 }
if a[u,v] < 0 then writeln( fo , -1 )
else begin
pt   := 1 ;
l[1] := u ;
truy_vet( u , v ) ;

write( fo , pt )  ;
for j := 1 to pt do write( fo , ' ', l[j] ) ;
writeln( fo ) ;
end ;
end ;
end ;

procedure process ;
var
k , u,  v : longint ;
begin
for k := 1 to n do { Floyd }
for u := 1 to n do
for v := u + 1 to n do
if a[u,v] > a[u,k] + a[k,v] then begin
a[u,v] := a[u,k] + a[k,v] ;
a[v,u] := a[u,v] ;
trace[u,v] := k  ;
trace[v,u] := k  ;
end ;

for u := 1 to n do
for v := 1 to n do
if a[u,v] = maxc then a[u,v] := -1 ; { Khong ton tai duong di }
end ;

procedure nhapdl ;
var
i , j,  u , v , val : longint ;
begin
read( fi , n , m , cau_hoi ) ;
for i := 1 to n do
for j := 1 to n do a[i,j] := maxc ;
for i := 1 to m do begin
read( fi , u , v , val ) ;
a[u,v] := val ;
a[v,u] := val ;
end ;

for i := 1 to n do a[i,i] := 0 ;
end ;

procedure mofile ;
begin
assign( fi , INP ) ; reset( fi )   ;
assign( fo , OUT ) ; rewrite( fo ) ;
end ;

procedure dongfile ;
begin
close( fi ) ; close( fo ) ;
end ;

BEGIN
mofile   ;
nhapdl   ;
process  ;
dongfile ;
END.


#### Code mẫu của khuc_tuan

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <cstdlib>
#include <ctime>
#include <string.h>

const int maxN = 100010;
const int oo = 1000000000;

using namespace std;

int n, m, kk, nheap;
int head[maxN], ke[maxN], next[maxN], ts[maxN], kq[maxN], h[maxN], pos[maxN], d[maxN], truoc[maxN];

void Doc(){
int x, y, z;
scanf("%d%d%d", &n, &m, &kk);
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &x, &y, &z);
ke[i] = y;
ts[i] = z;
ke[i + m] = x;
ts[i + m] = z;
}
}

void Doicho(int &x, int &y){
int tg = x;
x = y;
y = tg;
}

void Upheap(int i){
if ((i == 1) || (d[h[i / 2]] < d[h[i]])) return;
Doicho(h[i], h[i / 2]);
Doicho(pos[h[i]], pos[h[i / 2]]);
Upheap(i / 2);
}

void Downheap(int i){
int j = 2 * i;
if (j > nheap) return;
if (j < nheap && d[h[j]] > d[h[j + 1]]) j++;
if (d[h[i]] > d[h[j]]){
Doicho(h[i], h[j]);
Doicho(pos[h[i]], pos[h[j]]);
Downheap(j);
}
}

void Pus(int x){
nheap++;
h[nheap] = x;
pos[x] = nheap;
Upheap(nheap);
}

int Pop(){
int tg = h[1];
h[1] = h[nheap];
pos[h[1]] = 1;
nheap--;
Downheap(1);
return tg;
}

void Dijkstra(int u){
int j, v;
nheap = 0;
for(int i = 1; i <= n; i++){
pos[i] = 0;
truoc[i] = 0;
}
for(int i = 1; i <= n; i++) d[i] = oo;
d[u] = 0;
Pus(u);
do{
if (nheap == 0) break;
u = Pop();
//  cout << u << " " << d[u] <<  endl;
while (j != 0){
v = ke[j];
if (d[v] > d[u] + ts[j]){
d[v] = d[u] + ts[j];
truoc[v] = u;
if (pos[v] == 0) Pus(v);
else Upheap(pos[v]);
}
j = next[j];
}
}
while (true);
}

void Lam(){
int x, u, v, len;
for(int i = 1; i <= kk; i++){
scanf("%d%d%d", &x, &u, &v);
//cin >> x >> u >> v;
Dijkstra(u);
if (x == 0) printf("%d\n", d[v]);
else{
len = 0;
while (v != u){
len++;
kq[len] = v;
v = truoc[v];
}
len++;
kq[len] = u;
cout << len << " ";
for(int i = len; i >= 1; i--) cout << kq[i] << " ";
printf("\n");
}
}
}

void Inkq(){
}

int main()
{
//freopen("Floyd.inp", "r", stdin);
//freopen("Floyd.out", "w", stdout);
Doc();
Lam();
Inkq();
return 0;
}