「一本通 1.4 例 1」电路维修 最短路做法求助
  • 板块学术版
  • 楼主南瓜桐
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/12/5 18:15
  • 上次更新2023/11/3 22:49:55
查看原帖
「一本通 1.4 例 1」电路维修 最短路做法求助
439327
南瓜桐楼主2021/12/5 18:15

题目
打算先用Floyd试一下没想到爆0了...

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int r,c,t;
int map[2601][2601];
void sr(){
	char x;
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>x;
			if(x=='/'){
				map[(i-1)*c+j][i*c+j+1]=1;
				map[i*c+j+1][(i-1)*c+j]=1;
				map[(i-1)*c+j+1][i*c+j]=0;
				map[i*c+j][(i-1)*c+j+1]=0;
			}else{
				map[(i-1)*c+j+1][i*c+j]=1;
				map[i*c+j][(i-1)*c+j+1]=1;
				map[(i-1)*c+j][i*c+j+1]=0;
				map[i*c+j+1][(i-1)*c+j]=0;
			}	
		}
	}
//	cout<<endl;
//	for(int i=1;i<=(r+1)*(c+1);i++){
//		for(int j=1;j<=(r+1)*(c+1);j++){
//				if(map[i][j]==1){
//					cout<<i<<"-"<<j<<' '<<1<<endl;
//				}
//				if(map[i][j]==0){
//					cout<<i<<"-"<<j<<' '<<0<<endl;
//				}
//		}
//	}
}
int main(){
//	cin>>t;
	t=1;
	while(t--){
		for(int i=1;i<=2600;i++)
		{
			for(int j=1;j<=2600;j++){
				map[i][j]=10;
			}
		}
		sr();
		
		for(int k=1;k<=(r+1)*(c+1);k++){
			for(int i=1;i<=(r+1)*(c+1);i++){
				for(int j=1;j<=(r+1)*(c+1);j++){
					if((map[i][k]!=2147483647) && (map[k][j]!=2147483647) && (map[i][k]+map[k][j]<map[i][j])){
						map[i][j]=map[i][k]+map[k][j];
					}
				}
			}
		}
		cout<<map[1][(r+1)*(c+1)];
	}
	return 0;
}

Orz

2021/12/5 18:15
加载中...