Problem Description
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?
Input
输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
AC代码~~~~
********************************************
#include"stdio.h"
#include"string.h"
#define MAX 10000000
int map[101][101];
int v[101],d[101];
int main()
{
int N,M,A,B,C,i,j,pos,min;
while(scanf("%d%d",&N,&M),N!=0&&M!=0)
{
memset(v,0,sizeof(v));
for(i=1;i<=N;i++)
{
d[i]=MAX;
for(j=1;j<=N;j++)
map[i][j]=MAX;
map[i][i]=0;
}
for(i=1;i<=M;i++)
{
scanf("%d%d%d",&A,&B,&C);
if(C<map[A][B])
map[A][B]=map[B][A]=C;
}
pos=1;
v[pos]=1;
d[pos]=0;
for(i=1;i<=N;i++)
{
min=MAX;
for(j=1;j<=N;j++)
{
if(v[j]==0 && map[pos][j]!=MAX && (d[pos]+map[pos][j])<d[j])
{
d[j]=map[pos][j]+d[pos];
}
}
for(j=1;j<=N;j++)
{
if(v[j]==0&&d[j]<min)
{
min=d[j];
pos=j;
}
}
v[pos]=1;
}
printf("%d\n",d[N]);
}
return 0;
}
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?
Input
输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
AC代码~~~~
********************************************
#include"stdio.h"
#include"string.h"
#define MAX 10000000
int map[101][101];
int v[101],d[101];
int main()
{
int N,M,A,B,C,i,j,pos,min;
while(scanf("%d%d",&N,&M),N!=0&&M!=0)
{
memset(v,0,sizeof(v));
for(i=1;i<=N;i++)
{
d[i]=MAX;
for(j=1;j<=N;j++)
map[i][j]=MAX;
map[i][i]=0;
}
for(i=1;i<=M;i++)
{
scanf("%d%d%d",&A,&B,&C);
if(C<map[A][B])
map[A][B]=map[B][A]=C;
}
pos=1;
v[pos]=1;
d[pos]=0;
for(i=1;i<=N;i++)
{
min=MAX;
for(j=1;j<=N;j++)
{
if(v[j]==0 && map[pos][j]!=MAX && (d[pos]+map[pos][j])<d[j])
{
d[j]=map[pos][j]+d[pos];
}
}
for(j=1;j<=N;j++)
{
if(v[j]==0&&d[j]<min)
{
min=d[j];
pos=j;
}
}
v[pos]=1;
}
printf("%d\n",d[N]);
}
return 0;
}
发表评论
-
杭电1162 最小生成树问题
2012-07-27 15:15 857题目链接:http://acm.hdu.edu.cn/show ... -
杭电1596 迪杰特斯拉算法的应用
2012-07-25 20:47 1064题目 Problem Description XX星球有很多 ... -
杭电2680 迪杰特斯拉算法的应用
2012-07-25 20:43 1045题目描述: Problem Description: One ... -
杭电1272
2012-07-18 15:13 829这道题主要就是判断一下有没有环,还有就是节点数减去边数等于1, ... -
迪杰斯特拉(Dijkstra)算法
2012-07-17 16:07 1462迪杰斯特拉算法 迪杰斯特拉(Dijkstra)算法思想 ... -
杭电acm部分题目分类
2012-07-07 16:38 3423注:DP代表动态规划 1001 这个就不用说了吧 ... -
动态规划之背包问题
2012-07-07 16:22 838/*在一固定容积为C的背包内装入N件物品, 物品的体积为:w ... -
动态规划之背包问题
2012-07-07 16:12 0/*在一固定容积为C的背包内装入N件物品, 物品的体积为:w1 ... -
背包问题
2012-07-07 10:44 0决策是:第N件物品放或者不放; 由此可以写出动态转移方 ... -
杭电1003代码
2012-07-07 10:24 938#include<stdio.h> int mai ... -
动态规划
2012-07-07 10:21 748动态规划算法 一、基本 ...
相关推荐
在这个课设中,它可能被用来计算从校园的某个地点到其他所有地点的最短路径,这对于创建一个高效的校园导航系统至关重要。 最后,深度优先搜索(DFS)是一种遍历或搜索树或图的算法。在本项目的校园导游系统中,DFS...
- Dijkstra算法用于求单源最短路径,Floyd算法用于求所有顶点间的最短路径。 13. **数据结构在实际应用中的体现** - 在信息安全中,二叉树可用于加密通信,MD5算法用于信息完整性验证。 - 在生活中,数据结构如...
【描述】中的关键词"贪心"、"递归"、"分治"、"动态规划"、"RMQ"(Range Minimum Query,范围最小值查询)、"SPFA"(Shortest Path Faster Algorithm,最短路径快速算法)、"Bellman-Ford"、"DFS"(深度优先搜索)、...
4. 图:理解图的概念,包括图的存储方式(邻接矩阵、邻接表),图的遍历(深度优先搜索、广度优先搜索),最短路径问题(Dijkstra算法、Floyd算法),最小生成树问题(Prim算法、Kruskal算法)。 5. 排序与查找:...
例如,在需要找到最短路径的情况下,广度优先搜索更为适用;而在需要遍历所有可能的路径时,则深度优先搜索更加合适。 #### 1016 - 搜索与博弈策略 这道题目涉及搜索算法在博弈问题中的应用。在解决这类问题时,...
- OSPF(开放最短路径优先)是一种内部网关协议(IGP),用于在自治系统内计算最短路径树。实验可能涵盖OSPF区域划分、邻居关系建立、LSA(链路状态通告)的理解和路由计算。 5. **RIP路由协议配置**:2.3.2 RIP...
3. **图**:图的表示(邻接矩阵、邻接表)、图的遍历(深度优先搜索DFS、广度优先搜索BFS)以及图的特殊类型,如树、有向无环图DAG、最短路径问题(Dijkstra算法、Floyd-Warshall算法)。 4. **排序**:快速排序、...
在这个项目中,学生被要求编写一个程序,该程序能够为用户提供杭电校园内从一个景点到另一个景点的最短路径咨询服务。以下是这个报告中的关键知识点: 1. **图的抽象数据类型 (ADT Graph)**: 在需求分析中,首先...
而基础图论问题可能包括最短路径、最小生成树等。 2046题可能更倾向于数据结构的运用,比如二叉树、链表、堆、队列或栈等。这些数据结构在解决实际问题时有着广泛的应用,例如在搜索、排序、优先级队列等方面。 ...
4. **图论**:讲解最短路径、最小生成树、网络流等图论问题及其对应的算法,如Dijkstra、Floyd、Prim、Kruskal、Ford-Fulkerson等。 5. **数学应用**:介绍组合数学、数论、几何等在编程中的应用,帮助解决一些需要...
而图论则研究如何在图模型中寻找路径、循环和其他结构,常用于解决网络流量、最短路径等问题。 1005题可能是关于字符串处理或模式匹配的题目。字符串处理涉及到字符数组的操作,包括查找、替换、反转和模式匹配。...
本题采用广度优先搜索来寻找从起点到终点的最短路径。BFS是一种图遍历算法,它从根节点开始,然后遍历所有相邻节点,再遍历它们的所有相邻节点,以此类推。对于此类寻找最短路径的问题,BFS非常适合。 #### 2. ...
2. 图论算法:如Dijkstra最短路径算法、Floyd-Warshall所有对最短路径、Bellman-Ford负权边检测等,它们是解决复杂网络问题的关键。 3. 动态规划:通过状态转移方程解决最优化问题,如斐波那契数列、背包问题、最长...
常见的数据结构如数组、链表、栈、队列、树、图等,以及排序算法(快速排序、归并排序、堆排序)、查找算法(二分查找、哈希查找)和图论算法(最短路径、最小生成树)都是解题的关键。 3. **C/C++编程**:虽然主要...
2. 贪心算法的应用实例,如霍夫曼编码、Prim最小生成树算法、Dijkstra最短路径算法等,通过实例帮助学生理解贪心算法的工作原理。 3. 贪心算法的局限性,强调虽然贪心算法在某些问题上表现优秀,但并非所有问题都能...
- **最短路径问题**:寻找图中两点间最短的路径。 - **最小生成树**:在加权图中找到一棵包含所有顶点且权重最小的树。 - **网络流问题**:研究如何在网络中最大化流量的问题。 ### 五、组合数学 #### 排列与组合 ...
3. **熟悉常用算法**: 熟练运用排序(快速排序、归并排序、堆排序等)、查找(二分查找、哈希查找等)、图论算法(深度优先搜索、广度优先搜索、最小生成树、最短路径等)。 4. **逻辑思维与问题分析能力**: 能够...
- 图:图论是ACM竞赛中的核心部分,如最短路径(Dijkstra、Floyd)、最小生成树(Prim、Kruskal)等。 2. **排序与搜索算法** - 冒泡排序、插入排序、选择排序:基础排序算法,用于理解排序原理。 - 快速排序、...
- 这个文档可能是前一个答案文档的补充,可能包含了更多题目或者不同阶段的题目解答,可能涵盖了更多类型的算法和数据结构,比如哈希表、堆、图的最小生成树算法(Prim或Kruskal)、最短路径算法(Dijkstra或Floyd-...
- **1029**:可能是关于区间覆盖或者最短路径的问题,需要考虑如何使用DP来优化解决方案。 - **1114**:此类题目可能涉及到一维或二维数组的状态转移,比如编辑距离问题。 - **1284**:可能涉及到多个阶段的状态转移...