[uva] 10099 - The Tourist Guide
2024-08-30 17:26:33
10099 - The Tourist Guide
题目页：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1040
打不开的可以上国内的：http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1080
之前使用 最小生成树的 Kruskal 算法 + 广度优先搜索
改进之后用了 用动态规划技术实现的所有节点对的最短路径问题的 Floyd-Warshall 算法，不仅代码量急剧减少，简化了逻辑
此题的坑之一：Mr.G.自己也算一个人……… 反映到代码里是63行
|
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
|
#include <stdio.h>#include <stdlib.h>int number_points;int map_values[110][110];void floyd(){ for (int a = 1; a <= number_points; a++) { for (int b = 1; b <= number_points; b++) { for (int x = 1; x <= number_points; x++) { int ax = map_values[a][x]; int xb = map_values[x][b]; int smaller = ax < xb ? ax : xb; if (map_values[a][b] < smaller) { map_values[a][b] = smaller; } } } }}int main(){ int count = 1; int number_ways; scanf("%d%d", &number_points, &number_ways); while(number_points != 0 && number_ways != 0) { // 0. 初始化图 for (int y = 1; y <= number_points; y++) for (int x = 1; x <= number_points; x++) { map_values[x][y] = 0; } // 1. 读取边 for (int i = 0; i < number_ways; i++) { int x, y, values; scanf("%d%d%d", &x, &y, &values); map_values[x][y] = values; map_values[y][x] = values; } // 2. 读取起始节点和顾客数量 int start, end, number_customer; scanf("%d%d%d", &start, &end, &number_customer); // 3. floyd 算法 floyd(); // 4. 获取值 int max_value = map_values[start][end]; // 5. 输出结果 max_value--; // Mr. G. 自己也算上 int remainder = number_customer % max_value; printf("Scenario #%d\nMinimum Number of Trips = ", count); if (remainder) printf("%d\n", number_customer / max_value + 1); else printf("%d\n", number_customer / max_value); // 6. 读取下一行数据 scanf("%d%d", &number_points, &number_ways); count++; } return 0;} |
最新文章
- javascript中的变量
- PHPStorm技巧篇 -- 观感优化
- python 获取html源代码里标签之间的文本用get_text()
- [系统集成] 部署 mesos-exporter 和 prometheus 监控 mesos task
- [工具]Swagger-api接口文档描述
- Internetware网构软件（摘抄）
- Java关键字final、static使用总结(转)
- hdu 1403 Longest Common Substring(最长公共子字符串)（后缀数组）
- [读书笔记]算法(Sedgewick著)·第一章(2)
- svg滤镜学习
- 进阶之初探nodeJS
- 如何在不使用系统函数的情况下实现PHP中数组系统函数的功能
- c# redis 操作类库推荐：StackExchange.Redis.Extensions
- 是否可能两个ETH私钥对应同一个地址
- 解决ASP.NET MVC 检测到有潜在危险的 Request.Form 值
- How Many Processes Should Be Set For The Receiving Transaction Manager (RTM)
- python+selenium+xpath 爬取天眼查工商基本信息
- MAC操作系统使用小技巧
- Django多表操作
- jq获取图片并转换为base64