社区讨论

发现一个及其奇妙的事情......

sshijihong
P1529[USACO2.4] 回家 Bessie Come Home参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo2sn3e3
此快照首次捕获于
2023/10/23 19:07
2 年前
此快照最后确认于
2023/10/23 19:07
2 年前
查看原帖
这题我是用floyd做的，但跑一遍Floyd只能得55分（代码如下）
CPP
#include <iostream>
#include <queue>
using namespace std;
int dp[140][140];
int main(){
	int p;
	cin>>p;
	for(int i=1;i<=130;i++)
		for(int j=1;j<=130;j++) dp[i][j]=1e9;
	for(int i=1;i<=130;i++) dp[i][i]=0;
	for(int i=1;i<=p;i++){
		char c1,c2;
		int d;
		cin>>c1>>c2>>d;
		dp[c1][c2]=min(dp[c1][c2],d);
		dp[c2][c1]=min(dp[c2][c1],d);
	}
	for(int i=1;i<=130;i++)
		for(int j=1;j<=130;j++)
			for(int k=1;k<=130;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	int res=1e9;
	char c='A';
	for(int i=1;i<=130;i++){
		if(dp['Z'][i]>=1e9) continue;
		if(i>='A' and i<'Z')
			if(res>dp['Z'][i]){
				res=dp['Z'][i];
				c=i;
			}
	}
	cout<<c<<" "<<res<<endl;
}
跑两遍就能得88分：
CPP
#include <iostream>
#include <queue>
using namespace std;
int dp[140][140];
int main(){
	int p;
	cin>>p;
	for(int i=1;i<=130;i++)
		for(int j=1;j<=130;j++) dp[i][j]=1e9;
	for(int i=1;i<=130;i++) dp[i][i]=0;
	for(int i=1;i<=p;i++){
		char c1,c2;
		int d;
		cin>>c1>>c2>>d;
		dp[c1][c2]=min(dp[c1][c2],d);
		dp[c2][c1]=min(dp[c2][c1],d);
	}
	for(int i=1;i<=130;i++)
		for(int j=1;j<=130;j++)
			for(int k=1;k<=130;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	for(int i=1;i<=130;i++)
		for(int j=1;j<=130;j++)
			for(int k=1;k<=130;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	int res=1e9;
	char c='A';
	for(int i=1;i<=130;i++){
		if(dp['Z'][i]>=1e9) continue;
		if(i>='A' and i<'Z')
			if(res>dp['Z'][i]){
				res=dp['Z'][i];
				c=i;
			}
	}
	cout<<c<<" "<<res<<endl;
}
跑四遍就能AC
CPP
#include <iostream>
#include <queue>
using namespace std;
int dp[140][140];
int main(){
	int p;
	cin>>p;
	for(int i=1;i<=130;i++)
		for(int j=1;j<=130;j++) dp[i][j]=1e9;
	for(int i=1;i<=130;i++) dp[i][i]=0;
	for(int i=1;i<=p;i++){
		char c1,c2;
		int d;
		cin>>c1>>c2>>d;
		dp[c1][c2]=min(dp[c1][c2],d);
		dp[c2][c1]=min(dp[c2][c1],d);
	}
	for(int i=1;i<=130;i++)
		for(int j=1;j<=130;j++)
			for(int k=1;k<=130;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	for(int i=1;i<=130;i++)
		for(int j=1;j<=130;j++)
			for(int k=1;k<=130;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	for(int i=1;i<=130;i++)
		for(int j=1;j<=130;j++)
			for(int k=1;k<=130;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	for(int i=1;i<=130;i++)
		for(int j=1;j<=130;j++)
			for(int k=1;k<=130;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	int res=1e9;
	char c='A';
	for(int i=1;i<=130;i++){
		if(dp['Z'][i]>=1e9) continue;
		if(i>='A' and i<'Z')
			if(res>dp['Z'][i]){
				res=dp['Z'][i];
				c=i;
			}
	}
	cout<<c<<" "<<res<<endl;
}
其他地方都没动，就是多跑几遍Floyd，为什么分数就会不一样，求大佬指点！

回复

共 4 条回复，欢迎继续交流。

正在加载回复...