Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
事实证明floyd也可以的,acc了! 开始把题目看错了!In Reply To:我用floyd为什么不行呢? dijkstra不是和floyd差不多么? 高手解释一下,谢谢!! Posted by:zhb_msqx at 2007-08-26 11:58:34 #include <iostream> #include <fstream> using namespace std; #define Max 100000 int n; int from,to; int d[110][110]; void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(d[i][k]+d[k][j]<d[i][j])d[i][j]=d[i][k]+d[k][j]; } } } } void init(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j)d[i][j]=0; else d[i][j]=Max; } } } void main(){ cin>>n>>from>>to; init(); for(int i=1;i<=n;i++){ int k; cin>>k; for(int j=1;j<=k;j++){ int t; cin>>t; if(j==1){ d[i][t]=0; }else{ d[i][t]=1; } } } floyd(); if(d[from][to]==Max){ cout<<-1<<endl; }else{ cout<<d[from][to]<<endl; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator