07-图4 哈利·波特的考试

浅浅的花香味﹌ 2022-07-24 11:29 188阅读 0赞

#include <stdio.h>
    
    int Min(int a, int b);
    int Max(int a, int b);
    
    int main(int argc, char const *argv[])
    {
    	int N, M;
    	scanf("%d %d", &N, &M);
    	int graph[N+1][N+1];
    	for (int i = 1; i <= N; i++){
    		for (int j = 1; j <= N; j++){
    			if (i == j)
    				graph[i][j] = 0;
    			else
    				graph[i][j] = -1;
    		}
    	}
    	int n1, n2, len;
    	for (int i = 0; i < M; i++){
    		scanf("%d %d %d", &n1, &n2, &len);
    		graph[n1][n2] = graph[n2][n1] = len;
    	}
            //Floyd算法
           for (int i = 1; i <= N; i++){
    		for (int k = 1; k <= N; k++){
    			if (graph[i][k] == -1)
    				continue;
    			for (int j = 1; j <= N; j++){
    				if (graph[k][j] == -1)
    					continue;
    				if (graph[i][j] == -1)
    					graph[i][j] = graph[j][i] = graph[i][k]+graph[k][j];
    				else
    					graph[i][j] = graph[j][i] = Min(graph[i][j], graph[i][k]+graph[k][j]);
    			}
    		}
    	}
    	int num = -1, lenth = 10000, tmp;
            //遍历多源最短路径的二维数组，找到每个点到其他点的最大路径的点，在这些点中取最小值
           for (int i = 1; i <= N; i++){
    		tmp = 0;
    		for (int j = 1; j <= N; j++){
    			if (i == j)
    				continue;
    			if (graph[i][j] == -1)
    				break;
    			tmp = Max(tmp, graph[i][j]);
    			if (tmp < lenth && j >= N){
    				num = i;
    				lenth = tmp;
    			}
    		}
    	}
    	if (num == -1)
    		printf("0\n");
    	else
    		printf("%d %d\n", num, lenth);
    	return 0;
    }
    
    int Min(int a, int b)
    {
    	if (a < b)
    		return a;
    	else
    		return b;
    }
    
    int Max(int a, int b)
    {
    	if (a > b)
    		return a;
    	else
    		return b;
    }