1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int inf=0x3f3f3ff; 5 const int M=128; 6 class Floyd{///多源最短路o(MV^3) 7     typedef int typec;///边权的类型 8     static const int MV=128;///点的个数 9     int n,i,j,k;10     typec mat[MV][MV];11 public:12     void init(int tn){///传入点的个数，下标0开始13         n=tn;14         for(i=0;i<n;i++)15             for(j=0;j<n;j++)16                 mat[i][j]=i==j?0:inf;17     }18     void add(int u,int v,typec w){19         mat[u][v]=min(mat[u][v],w);20     }21     void solve(){22         for(k=0; k<n; k++)23             for(i=0; i<n; i++)24                 for(j=0; j<n; j++)25                     mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);26     }27     typec getdist(int x,int y) {28         return mat[x][y];29     }30 }gx;31 int main() {32     int n,m,x,y;33     while(~scanf("%d",&n),n) {34         gx.init(n);35         for(int i=0; i<n; i++) {36             scanf("%d",&m);37             while(m--) {38                 scanf("%d%d",&x,&y);39                 gx.add(i,x-1,y);40             }41         }42         gx.solve();43         int sma=inf;44         int id;45         for(int i=0; i<n; i++) {46             int sum=0;47             for(int j=0; j<n; j++) {48                 sum+=gx.getdist(i,j);49             }50             if(sma>sum) {51                 sma=sum;52                 id=i;53             }54         }55         int big=0;56         for(int i=0; i<n; i++) {57             big=max(big,gx.getdist(id,i));58         }59         printf("%d %d\n",id+1,big);60     }61     return 0;62 }

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int inf=0x3f3f3f3f; 5 class Floyd { ///多源最短路o(MV^3) 6     typedef int typec;///边权的类型 7     static const int MV=128;///点的个数 8     int n,i,j,k; 9     typec mat[MV][MV];10 public:11     void init(int tn) { ///传入点的个数，下标0开始12         n=tn;13         for(i=0; i<n; i++)14             for(j=0; j<n; j++)15                 mat[i][j]=i==j?0:inf;16     }17     void add(int u,int v,typec w) {18         mat[u][v]=min(mat[u][v],w);19     }20     void solve() {21         for(k=0; k<n; k++)22             for(i=0; i<n; i++)23                 for(j=0; j<n; j++)24                     mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);25     }26     typec getdist(int x,int y) {27         return mat[x][y];28     }29 }gx;30 int main() {31     int n;32     char tmp[32];33     while(~scanf("%d",&n)) {34         gx.init(n);35         for(int i=2; i<=n; i++) {36             for(int j=1; j<i; j++) {37                 scanf("%s",tmp);38                 if(tmp[0]==‘x‘) {39                     continue;40                 }41                 int sum=0;42                 for(int k=0; tmp[k]; k++) {43                     sum*=10;44                     sum+=tmp[k]-‘0‘;45                 }46                 gx.add(i-1,j-1,sum);47                 gx.add(j-1,i-1,sum);48             }49         }50         gx.solve();51         int ans=0;52         for(int i=0; i<n; i++) {53             ans=max(ans,gx.getdist(0,i));54         }55         printf("%d\n",ans);56     }57     return 0;58 }

 1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<stack> 5 #include<algorithm> 6 #define mt(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 typedef __int64 LL; 9 const int inf=0x3f3f3f3f;10 class Floyd { ///多源最短路o(MV^3)11     typedef int typec;///边权的类型12     static const int MV=128;///点的个数13     int n,i,j,k;14     typec mat[MV][MV];15 public:16     void init(int tn) { ///传入点的个数，下标0开始17         n=tn;18         for(i=0; i<n; i++)19             for(j=0; j<n; j++)20                 mat[i][j]=i==j?0:inf;21     }22     void add(int u,int v,typec w) {23         mat[u][v]=min(mat[u][v],w);24     }25     void solve() {26         for(k=0; k<n; k++)27             for(i=0; i<n; i++)28                 for(j=0; j<n; j++)29                     mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);30     }31     typec getdist(int x,int y) {32         return mat[x][y];33     }34 }gx;35 int main(){36     int n,a,b;37     while(~scanf("%d%d%d",&n,&a,&b)){38         gx.init(n);39         for(int i=1;i<=n;i++){40             int m,to;41             scanf("%d",&m);42             for(int j=0;j<m;j++){43                 scanf("%d",&to);44                 if(j!=0)    gx.add(i-1,to-1,1);45                 else        gx.add(i-1,to-1,0);46             }47         }48         gx.solve();49         int ans=gx.getdist(a-1,b-1);50         if(ans>1024) ans=-1;51         printf("%d\n",ans);52     }53     return 0;54 }

 1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<queue> 5 #include<stack> 6 #include<algorithm> 7 #define mt(a,b) memset(a,b,sizeof(a)) 8 using namespace std; 9 typedef __int64 LL;10 const int inf=0x3f3f3f3f;11 const int M=210;12 class Floyd { ///多源最短路o(MV^3)13     typedef double typec;///边权的类型14     static const int MV=M;///点的个数15     int n,i,j,k;16     typec mat[MV][MV];17 public:18     void init(int tn) { ///传入点的个数，下标0开始19         n=tn;20         for(i=0; i<n; i++)21             for(j=0; j<n; j++)22                 mat[i][j]=i==j?0:inf;23     }24     void add(int u,int v,typec w) {25         mat[u][v]=min(mat[u][v],w);26     }27     void solve() {28         for(k=0; k<n; k++)29             for(i=0; i<n; i++)30                 for(j=0; j<n; j++)31                     mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);32     }33     typec getdist(int x,int y) {34         return mat[x][y];35     }36 }gx;37 struct point{38     double x,y;39 }p[M];40 double a[M][M];41 int main() {42     int i,j,c,flag=0;43     scanf("%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y);44     int n=2;45     while(~scanf("%lf%lf",&p[n].x,&p[n].y)) {46         if(p[n].x==-1&&p[n].y==-1) {47             flag=0;48             continue;49         }50         if(flag) {51             a[n][n-1]=sqrt((p[n].x-p[n-1].x)*(p[n].x-p[n-1].x)+(p[n].y-p[n-1].y)*(p[n].y-p[n-1].y))/40000.0;52             a[n-1][n]=a[n][n-1];53         }54         n++;55         flag=1;56     }57     for(i=0; i<n; i++) {58         for(j=0; j<n; j++) {59             if(i!=j&&a[i][j]==0.0) {60                 a[i][j]=sqrt((p[j].x-p[i].x)*(p[j].x-p[i].x)+(p[j].y-p[i].y)*(p[j].y-p[i].y))/10000.0;61             }62         }63     }64     gx.init(n);65     for(i=0;i<n;i++){66         for(j=0;j<n;j++){67             gx.add(i,j,a[i][j]);68         }69     }70     gx.solve();71     printf("%0.0f\n",60.0*gx.getdist(0,1));72     return 0;73 }