直接套floyd模板:
//floyd hoj 1211 #include <iostream> #include <cstdio> #define INF 999999 using namespace std; int map[101][101]; void floyd(int n) { for(int k=0; k<n; k++) { for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(map[i][j]>map[i][k]+map[k][j]) { map[i][j]=map[i][k]+map[k][j]; } } } } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; scanf("%d",&n); while(n--) { int v,e; scanf("%d %d",&v,&e); for(int i=0; i<v; i++) { for(int j=0; j<v; j++) { map[i][j]=(i==j)? 0:INF; } } int vertex1,vertex2,length; for(int i=0; i<e; i++) { scanf("%d %d %d",&vertex1,&vertex2,&length); map[vertex1][vertex2]=map[vertex2][vertex1]=length; } floyd(v); int temp=INF; int ans; for(int i=0; i<v; i++) { int sum=0; for(int j=0; j<v; j++) { sum+=map[i][j]; } if(temp>sum) { temp=sum; ans=i; } } printf("%d %d\n",ans,temp); } return 0; }