Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/floyd


Cho đơn đồ thị vô hướng N đỉnh và M cạnh, trọng số các cạnh đều nguyên dương. Có 2 loại câu hỏi :
0 u v : Cho biết đường đi ngắn nhất từ u tới v có độ dài là bao nhiêu.
1 u v : Hãy chỉ ra 1 đường đi ngắn nhất từ u => v
Bài cơ bản này nhằm kiểm tra kỹ năng xây dựng các module chương trình con dành cho truy vết 1 cách hợp lý, sử dụng nhuần nhuyễn chương trình con, lời gọi hàm .

Download test và solution tại đây

Input

Dòng 1 : 3 số nguyên N , M , K . ( 1 ≤ N ≤ 100 , 1 ≤ M ≤ N*(N-1)/2 , 1 ≤ K ≤ 1000 )
M dòng tiếp theo , dòng thứ i gồm 3 số nguyên dương u , v , c cho biết cạnh (u,v) có trọng số là c ( 1 ≤ c ≤ 10000 )
K dòng tiếp theo là K câu hỏi , dòng thứ j sẽ có định dạng như đã nêu ở trên .

Output

Ứng với mỗi câu hỏi trong K câu hỏi thì ta phải trả lời trên mỗi dòng như sau .
Câu hỏi 0 u v : Ghi ra 1 số nguyên duy nhất là độ dài đường đi ngắn nhất từ u -> v.
Câu hỏi 1 u v : Ghi ra số đầu tiên là số X là số đỉnh trên đường đi ngắn nhất này , tiếp đó ghi ra X số là chỉ số các đỉnh theo thứ tự xuất hiện trên hành trình .

Example

Input:
3 3 2
1 2 3
2 3 1
1 3 5
0 1 2
1 1 3

Output:
3
3 1 2 3

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2021-12-03 09:49:50
#include<stdio.h>
#define oo 10000001
int matrix[101][101],chuaxet[101],truoc[101],d[101],s[101],t[101],dem;
void input(int n,int m,int ch[],int q){
for(int i=0;i<=n;i++){
for(int j=1;j<=m;j++){
matrix[i][j]=oo;
}
}
int u,v,p;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&u,&v,&p);
matrix[u][v]=p;
matrix[v][u]=p;
}
for(int i=1;i<=q;i++){
scanf("%d %d %d",&ch[i],s[i],t[i]);
}
}
void dijkstra(int s,int t,int n){
for(int v=1;v<=n;v++){
chuaxet[v]=0;
d[v]=matrix[s][v];
truoc[v]=s;
}
chuaxet[s]=1;
truoc[s]=0;
d[s]=0;
int u;
while(!chuaxet[t]){
int mp=oo;
for(int v=1;v<=n;v++){
if(!chuaxet[v] and mp>d[v]){
u=v;
mp=d[v];
}
}
chuaxet[u]=1;
if(!chuaxet[t]){
for(int v=1;v<=n;v++){
if(!chuaxet[v] and d[v]>matrix[u][v]+d[u]){
truoc[v]=u;
d[v]=matrix[u][v]+d[u];
}
}
}
}
}
void duongdi(int i){
if(i!=0){
dem++;
duongdi(truoc[i]);
printf("%d ",i);
}
else if(i==0) printf("%d",dem);
}
void output(int ch[],int n,int q){
for(int i=1;i<=q;i++){
dijkstra(s[i],t[i],n);
if(ch[i]==0){
printf("%d",d[t[i]]);
}
if(ch[i]==1){
dem=0;
duongdi(t[i]);
}
printf("\n");
}
}
int main(){
int n,m,ch[101],q;
scanf("%d %d %d",&n,&m,&q);
input(n,m,ch,q);
output(ch,n,q);
}
sao sai vậy??
2021-07-16 12:55:53
Floyd cơ bản
2021-05-27 18:00:42
Tham khảo: https://vnspoj.github.io/problems/FLOYD
2020-07-24 05:58:49
nhật hào bẩn
2020-04-11 03:22:30
Moi nguoi cho em hoi test 9 la gi ma em sai hoai ko qua dc :((
2019-12-26 15:40:22
mịa nó mất cả tiếng debug vì quên để F[i,i] = 0 (lúc đầu đặt tất cả = oo), đúng là kinh nghiệm sương máu :))
2019-08-11 18:47:15
IT lazy AC nhé
2019-06-06 07:06:40
má :v accepted cứ tưởng chưa chạy hóa ra full rồi :v
2019-05-25 04:34:22
gáy lịch sự :))
2019-04-23 15:40:17
game eazzzyyy
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.