Floyd 求助
  • 板块学术版
  • 楼主E1_de5truct0r
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/5/15 11:24
  • 上次更新2023/11/4 23:15:23
查看原帖
Floyd 求助
195198
E1_de5truct0r楼主2021/5/15 11:24

RT,看了半个小时没看出来哪里错了(

站外题。题面:

#include <bits/stdc++.h>
#define rint register int
using namespace std;
int m,n,dp[505][505],a[505][505],len[505];
void Floyd()
{
    for(rint k=1;k<=n;k++)
        for(rint i=1;i<=n;i++)
            for(rint j=1;j<=n;j++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+1);  
	if(dp[1][n]==1e9) printf("NO");
	else printf("%d",dp[1][n]);
}
void read(int &w)
{
	w=0;char ch=getchar();int f=1;
	for(;!(ch>='0'&&ch<='9');ch=getchar())if(ch=='-')f=-1;
	for(;(ch>='0'&&ch<='9');ch=getchar())w=(w<<1)+(w<<3)+(ch^48);
	w*=f;
}
int main()
{
	for(rint i=0;i<=500;i++)
		for(rint j=0;j<=500;j++)
			if(i!=j) dp[i][j]=1e9;
	read(m);read(n);
	for(rint i=1;i<=m;i++)
	{
		string LOL;int w=0;
		getline(cin,LOL);
		for(int j=0;j<LOL.length();j++)
		{
			if(!isdigit(LOL[j])) a[i][++len[i]]=w,w=0;
			else w=(w<<1)+(w<<3)+(LOL[j]^48);
		}
		a[i][++len[i]]=w;
		for(int j=1;j<=len[i];j++)
			for(int k=j+1;k<=len[i];k++)
				dp[a[i][j]][a[i][k]]=0;
	}
//	for(int i=1;i<=n;i++,cout<<endl)
//		for(int j=1;j<=n;j++)
//			cout<<setw(10)<<dp[i][j]; 
	Floyd();
	return 0;
}
2021/5/15 11:24
加载中...