floyd多跑几遍就行了(我也是一样的问题),我也不知道为什么......
```cpp
#include<iostream>
#include<cstring>
using namespace std;
int getnum(char c) {
if(c>='a'&&c<='z')return c-'a'+26;
else return c-'A';
}
int n,a1,b1,d;
char a,b;
int dis[200][200],w[200];
int main() {
ios::sync_with_stdio(0);
for(int i='A'; i<='z'; i++){
for(int j='A'; j<='z'; j++) {
if(i!=j) dis[i][j]=99999999;
}
}
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a>>b>>d;
a1=int(a),b1=int(b);
if(a1>='A'&&a1<='Z'){
w[a1]=1;
}
if(b1>='A'&&b1<='Z'){
w[b1]=1;
}
dis[a1][b1]=min(dis[a1][b1],d);
dis[b1][a1]=min(dis[b1][a1],dis[a1][b1]);
}
for(int i='A'; i<='z'; i++)
for(int j='A'; j<='z'; j++)
for(int k='A'; k<='z'; k++)
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
for(int i='A'; i<='z'; i++)
for(int j='A'; j<='z'; j++)
for(int k='A'; k<='z'; k++)
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
for(int i='A'; i<='z'; i++)
for(int j='A'; j<='z'; j++)
for(int k='A'; k<='z'; k++)
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
for(int i='A'; i<='z'; i++)
for(int j='A'; j<='z'; j++)
for(int k='A'; k<='z'; k++)
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
int minnn=99999999;
char minx;
for(int i='A'; i<='Y'; i++) {
if(dis[i]['Z']<minnn&&w[i]==1) {
minnn=dis[i]['Z'],minx=char(i);
}
}
cout<<minx<<" "<<minnn<<endl;
return 0;
}
```
跑四遍floyd就满分了(跑两遍88分,跑一 遍55分)
by shijihong @ 2023-04-08 08:08:32
@[shijihong](/user/383601)
有没有一种可能,floyd最外面的循环才是k,而不是最里面的。。。
```
#include <bits/stdc++.h>
#define long long ll;
using namespace std;
int A[54][54],p,minn=INT_MAX;
void floyd(){
for (int k=1;k<=52;k++){
for (int i=1;i<=52;i++){
for (int j=1;j<=52;j++){
A[i][j]=min(A[i][j],A[i][k]+A[k][j]);
}
}
}
}
int main(){
memset(A,0x3f,sizeof(A));
cin>>p;
for (int i=1;i<=p;i++){
char a,b;
int c,a1,b1;
cin>>a>>b>>c;
if(a==b)continue;
if(a>='a'&&a<='z'){
a1=a-'a'+1;
}else a1=a-'A'+27;
if(b>='a'&&b<='z'){
b1=b-'a'+1;
}else b1=b-'A'+27;
A[a1][b1]=A[b1][a1]=min(c,A[a1][b1]);
}
floyd();
int r=1e9;
char s;
for (int i=27;i<52;i++){
if(A[i][52]<r){
s=i-27+'A';
r=A[i][52];
}
}
cout<<s<<" "<<r;
return 0;
}
```
而且如果重复floyd的话,包装成函数不会更好看吗?
by BensonChen @ 2023-10-12 16:29:23