这题我是用floyd做的，但跑一遍Floyd只能得55分（代码如下）

#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分：

#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

#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，为什么分数就会不一样，求大佬指点！