1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
| #include <stdlib.h> #include <stdio.h>
#define MaxAnimal 105 #define Inf 65535
typedef struct GNode* PtrToGraph; struct GNode { int V,E; int G[MaxAnimal][MaxAnimal]; }; typedef PtrToGraph MGraph;
MGraph CreateGraph(int V,int E) { int i,j,V1,V2,Num; MGraph Graph; Graph = (MGraph)malloc(sizeof(struct GNode)); Graph->V = V; Graph->E = E; for(i = 0;i < V;i++) for(j = 0;j < V; j++) { if(i == j) Graph->G[i][j] = 0; else Graph->G[i][j] = Inf; } for(i = 0;i < E;i++) { scanf("%d %d %d\n",&V1,&V2,&Num); Graph->G[V1-1][V2-1] = Num; Graph->G[V2-1][V1-1] = Num; } return Graph; } int FindMaxDist(int D[][MaxAnimal],int i, int V) { int MaxDist,j; MaxDist = 0; for(j=0;j<V;j++) if(i!=j && D[i][j]>MaxDist) MaxDist = D[i][j]; return MaxDist; } void Floyd(MGraph Graph,int D[][MaxAnimal]) { int i,j,k; for(i = 0;i<Graph->V;i++) for(j = 0;j<Graph->V;j++) D[i][j] = Graph->G[i][j]; for(k = 0;k<Graph->V;k++) for(i = 0;i<Graph->V;i++) for(j = 0;j<Graph->V;j++) if(D[i][k] + D[k][j] < D[i][j]) D[i][j] = D[i][k] + D[k][j]; }
void Findanimal(MGraph Graph) { int D[MaxAnimal][MaxAnimal]; int Animal,i,MinDist,MaxDist; Floyd(Graph,D); MinDist = Inf; for(i=0;i<Graph->V;i++){ MaxDist = FindMaxDist(D,i,Graph->V); if(MinDist > MaxDist) { MinDist = MaxDist; Animal = i+1; } if(MaxDist == Inf) { printf("0\n"); return; } } printf("%d %d\n",Animal,MinDist); } int main() { int V,E; scanf("%d %d\n",&V,&E); MGraph Graph; Graph = CreateGraph(V,E); Findanimal(Graph); return 0; }
|