CSES - Shortest Routes II | Tuyến đường ngắn nhất II
Xem PDF
Điểm:
1400 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Có \(n\) thành phố và \(m\) con đường giữa chúng. Nhiệm vụ của bạn là hãy xử lý \(q\) truy vấn mà trong đó bạn phải xác định độ dài của tuyến đường ngắn nhất giữa hai thành phố cho trước.
Input
- Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\) và \(q\): số lượng thành phố, con đường và truy vấn.
- Sau đó, có \(m\) dòng mô tả các con đường. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): có một con đường giữa các thành phố \(a\) và \(b\) mà độ dài của nó là \(c\). Tất cả con đường đều là con đường hai chiều.
- Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên \(a\) và \(b\): xác định độ dài của tuyến đường ngắn nhất giữa các thành phố \(a\) và \(b\).
Output
- In độ dài của tuyến đường ngắn nhất với mỗi truy vấn. Nếu không có tuyến đường nào, in \(-1\) thay vào đó.
Constraints
- \(1 \le n \le 500\)
- \(1 \le m \le n^2\)
- \(1 \le q \le 10^5\)
- \(1 \le a,b \le n\)
- \(1 \le c \le 10^9\)
Example
Sample input
4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2
Sample output
5
5
8
-1
3
Bình luận
pragma GCC optimize("unroll-loops,02,no-stack-protector")
pragma GCC optimize("O3")
pragma GCC optimize("O1")
pragma GCC optimize("O1")
pragma GCC target("avx2")
pragma GCC optimize("unroll-loops")
pragma GCC target("avx")
pragma GCC optimize(3)
pragma GCC optimize("Ofast")
pragma GCC optimize("inline")
pragma GCC optimize("-fgcse")
pragma GCC optimize("-fgcse-lm")
pragma GCC optimize("-fipa-sra")
pragma GCC optimize("-ftree-pre")
pragma GCC optimize("-ftree-vrp")
pragma GCC optimize("-fpeephole2")
pragma GCC optimize("-ffast-math")
pragma GCC optimize("-fsched-spec")
pragma GCC optimize("-falign-jumps")
pragma GCC optimize("-falign-loops")
pragma GCC optimize("-falign-labels")
pragma GCC optimize("-fdevirtualize")
pragma GCC optimize("-fcaller-saves")
pragma GCC optimize("-fcrossjumping")
pragma GCC optimize("-fthread-jumps")
pragma GCC optimize("-freorder-blocks")
pragma GCC optimize("-fschedule-insns")
pragma GCC optimize("inline-functions")
pragma GCC optimize("-ftree-tail-merge")
pragma GCC optimize("-fschedule-insns2")
pragma GCC optimize("-fstrict-aliasing")
pragma GCC optimize("-falign-functions")
pragma GCC optimize("-fcse-follow-jumps")
pragma GCC optimize("-fsched-interblock")
pragma GCC optimize("-fpartial-inlining")
pragma GCC optimize("no-stack-protector")
pragma GCC optimize("-freorder-functions")
pragma GCC optimize("-findirect-inlining")
pragma GCC optimize("-fhoist-adjacent-loads")
pragma GCC optimize("-frerun-cse-after-loop")
pragma GCC optimize("inline-small-functions")
pragma GCC optimize("-finline-small-functions")
pragma GCC optimize("-ftree-switch-conversion")
pragma GCC optimize("-foptimize-sibling-calls")
pragma GCC optimize("-fexpensive-optimizations")
pragma GCC optimize("inline-functions-called-once")
pragma GCC optimize("-fdelete-null-pointer-checks")
pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,mmx,abm")
uses math;
var a,b,c,q,d,i,n,u,m,v,x:int64;
s:array[0..501,0..501] of int64;
vi:array[0..501,0..501] of boolean;
t1:text;
begin
read(m,n,q);
fillchar(vi,sizeof(vi),false);
for i:=1 to n do
begin
read(u,v,x);
if vi[u,v] then
begin
s[u,v]:=min(s[u,v],x);
s[v,u]:=s[u,v];
end
else
begin
s[u,v]:=x;
s[v,u]:=x;
end;
vi[u,v]:=true;
vi[v,u]:=true;
end;
for i:=1 to m do
for a:=1 to m do
for b:=1 to m do
if a=b then
continue
else
if not(vi[a,b]) and (vi[i,a]) and (vi[i,b]) then
begin
vi[a,b]:=true;
s[a,b]:=s[i,a]+s[i,b];
end
else
if (s[a,b]>s[i,a]+s[i,b]) and (vi[i,a]) and (vi[i,b]) then
s[a,b]:=s[i,a]+s[i,b];
for i:=1 to q do
begin
read(u,v);
if u=v then
writeln(0)
else
if not(vi[u,v]) then
writeln(-1)
else
writeln(s[u,v]);
end;
end.
(pascal)
https://cses.fi/paste/e7410f352b317deb8159d1/