| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
FLOYD - Floyd hoặc Dijkstra ( Cơ bản ) |
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 |
|||||||||||
RSS