Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

事实证明floyd也可以的,acc了! 开始把题目看错了!

Posted by zhb_msqx at 2007-08-26 14:35:46 on Problem 1847
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator