| ||||||||||
| 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