网站建设入门教程pdf,wordpress 英文 企业网站模板,app软件下载网站免费进入,临沂建设大型网站建设题目描述#xff1a;
在每年的校赛里#xff0c;所有进入决赛的同学都会获得一件很漂亮的 T-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候#xff0c;却是非常累的#xff01;所以现在他们想要寻找最短的从商店到赛场的路线#xff0c;你可以帮助…题目描述
在每年的校赛里所有进入决赛的同学都会获得一件很漂亮的 T-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候却是非常累的所以现在他们想要寻找最短的从商店到赛场的路线你可以帮助他们吗
输入输出格式 输入格式 第一行是两个整数 N,MN 表示成都的大街上有几个路口标号为 1 的路口是商店所在地标号为 N 的路口是赛场所在地M 则表示在成都有几条路。 接下来 M 行每行包括三个整数 ABC表示在路口 A 与路口 B 之间有一条路我们的工作人员需要 C 分钟的时间走过这条路。 输入保证至少存在 1 条商店到赛场的路线。 输出格式 输出一行表示工作人员从商店走到赛场的最短时间。
输入输出样例1 输入 3 3 1 2 5 2 3 5 3 1 2 输出 2
输入输出样例2 输入 2 1 1 2 3 输出 3
具体代码 #includestdio.h
int main(void)
{ int arr[100][100] { 0 };//构建图 int n, m; scanf(%d%d, n, m); int a, b,c; for (int i 1; i n; i) for (int j 1; j n; j) if (i j) arr[i][j] 0; else arr[i][j] 99999999;//初始化图。 for (int i 0; i m; i) { scanf(%d%d%d, a, b, c); arr[a][b] c; arr[b][a] c; }//根据输入为图赋值。 for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) if (arr[i][j] arr[i][k] arr[k][j]arr[i][k]99999999arr[k][j]99999999) arr[i][j] arr[i][k] arr[k][j];//Floyd—warshall核心代码。 printf(%d, arr[1][n]);//打印结果
} 代码解析 关于构件图和为图初始化赋值是上节课的答案在此我们就不进行讲述。 实际上Floyd-Warshall算法是较为容易理解的算法因其核心代码只有5行。 for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) if (arr[i][j] arr[i][k] arr[k][j]arr[i][k]99999999arr[k][j]99999999) arr[i][j] arr[i][k] arr[k][j]; 讲述起来很简单我们先看后四行代码假设k 1. for (int i 1; i n; i) for (int j 1; j n; j) if (arr[i][j] arr[i][1] arr[1][j]arr[i][1]99999999arr[1][j]99999999) arr[i][j] arr[i][k] arr[k][j]; arr[i][1]arr[1][j]表示i通过1到j的路程。 如果从i直接到j的路程比通过1的路程要长的化更新arr[i][j]的值变短。如果再来一次这段代码这次k值为2表示让arr[i][j]与让i通过12到j的值进行比较更新arr[i][j],然后继续让k等于345n这样就能更新全图可以得到任意两点的最短路径。 arr[i][1]99999999arr[1][j]99999999而这也是个判断条件如果这两点有任意一个路不通就不执行最后一条语句这也很容易理解如果路不通也就不能走了。 温馨提示 这段代码并不是专门求单源最短路径而是可以得出任意两点的最短路径。 这段代码核心只有5行理解不了直接背下来也是很容易的可以在往后的实践中逐渐搞明白。
