FLOYD spoj – Floyd hoặc Dijkstra ( Cơ bản )

const fi='; nmax=100; vc=100000;//high(longint); type data=longint; var f:text; n,m,k:data; A:array[0..nmax+1,0..nmax+1] of data; D:array[0..nmax+1] of data; free:array[0..nmax+1] of boolean; trace:array[0..nmax+1] of data; luu:array[0..nmax+1] of data; spt:data; procedure dijkstra(s,t:data); var i,j,u,v,min:data; begin for i:=1 to n do begin free[i]:=true; d[i]:=a[s,i]; trace[i]:=s; end; repeat min:=vc; u:=0; for i:=1 to n do if (free[i]) and (d[i]<min) then begin min:=d[i]; u:=i; end; if (u=0) or (u=t) then break; free[u]:=false; for v:=1 to n do begin if (free[v]) and (d[v]>d[u]+a[u,v]) then begin d[v]:=d[u]+a[u,v]; trace[v]:=u; end; end; until FALSE; end; procedure truyvet(v:data); var x:data; i:data; begin if trace[v]<>0 then begin truyvet(trace[v]); inc(spt); luu[spt]:=v; end else begin inc(spt); luu[spt]:=v; end; end; procedure docfile; var i,j,u,v,c,tl:data; begin assign(f,fi); reset(f); readln(f,n,m,k); for i:=1 to n do for j:=1 to n do if i=j then a[i,j]:=0 else a[i,j]:=vc; for i:=1 to m do begin readln(f,u,v,c); a[u,v]:=c; a[v,u]:=c; end; for i:=1 to k do begin readln(f,tl,u,v); if tl=0 then begin dijkstra(u,v); writeln(d[v]); end else begin dijkstra(u,v); if u<>v then begin spt:=0; trace[u]:=0; truyvet(v); write(spt,' '); for j:=1 to spt do write(luu[j],' '); writeln; end else writeln('2 ',u,' ',v); end; end; close(f); end; begin docfile; readln; end.

#include <bits/stdc++.h> using namespace std; const int maxn=100; const int maxd=10e6; int n,m,k; int a[maxn][maxn]; void Init() { scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=maxd; int u,v,c; for (int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&c); a[u][v]=c; a[v][u]=c; } } void Solve() { while(k--) { int t,u, v; scanf("%d%d%d",&t,&u,&v); vector<int> L(n+2,0); vector<int> Prev(n+2,0); vector<int> Visit(n+2,0); for (int i=1;i<=n;i++) L[i]=maxd; L[u]=0; while(1) { int u=0; int min1=maxd; for (int i=1;i<=n;i++) { if(!Visit[i] && L[i]<min1) { min1=L[i]; u=i; } } if(u==0 || u==v) break; Visit[u]=1; for (int i=1;i<=n;i++) { if(!Visit[i] && L[i]>L[u]+a[u][i]) { L[i]=L[u]+a[u][i]; Prev[i]=u; } } } if(t==0) { printf("%dn",L[v]); } else { stack<int> st; while(v != u) { st.push(v); v=Prev[v]; } printf("%d %d ",st.size()+1,u); while(!st.empty()) { printf("%d ",st.top()); st.pop(); } printf("n"); } } } int main() { Init(); Solve(); }