`
玉箫客
  • 浏览: 12678 次
最近访客 更多访客>>
社区版块
存档分类
最新评论

杭电2544 最短路径

c 
阅读更多
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;
}

分享到:
评论

相关推荐

    杭电数据结构课设(自选题)

    在这个课设中,它可能被用来计算从校园的某个地点到其他所有地点的最短路径,这对于创建一个高效的校园导航系统至关重要。 最后,深度优先搜索(DFS)是一种遍历或搜索树或图的算法。在本项目的校园导游系统中,DFS...

    杭电计算机考研复试专业课问题.pdf

    - Dijkstra算法用于求单源最短路径,Floyd算法用于求所有顶点间的最短路径。 13. **数据结构在实际应用中的体现** - 在信息安全中,二叉树可用于加密通信,MD5算法用于信息完整性验证。 - 在生活中,数据结构如...

    lanqiao_杭电ACMOJ解题报告_规划_

    【描述】中的关键词"贪心"、"递归"、"分治"、"动态规划"、"RMQ"(Range Minimum Query,范围最小值查询)、"SPFA"(Shortest Path Faster Algorithm,最短路径快速算法)、"Bellman-Ford"、"DFS"(深度优先搜索)、...

    杭电数据结构考研资料

    4. 图:理解图的概念,包括图的存储方式(邻接矩阵、邻接表),图的遍历(深度优先搜索、广度优先搜索),最短路径问题(Dijkstra算法、Floyd算法),最小生成树问题(Prim算法、Kruskal算法)。 5. 排序与查找:...

    杭电ACM 题目分类 不完全 记录搜索,递归求解

    例如,在需要找到最短路径的情况下,广度优先搜索更为适用;而在需要遍历所有可能的路径时,则深度优先搜索更加合适。 #### 1016 - 搜索与博弈策略 这道题目涉及搜索算法在博弈问题中的应用。在解决这类问题时,...

    HDU杭电 计算机网络实验报告

    - OSPF(开放最短路径优先)是一种内部网关协议(IGP),用于在自治系统内计算最短路径树。实验可能涵盖OSPF区域划分、邻居关系建立、LSA(链路状态通告)的理解和路由计算。 5. **RIP路由协议配置**:2.3.2 RIP...

    杭电数据结构01-16年真题

    3. **图**:图的表示(邻接矩阵、邻接表)、图的遍历(深度优先搜索DFS、广度优先搜索BFS)以及图的特殊类型,如树、有向无环图DAG、最短路径问题(Dijkstra算法、Floyd-Warshall算法)。 4. **排序**:快速排序、...

    数据机结构课程设计 校园导游咨询实习报告

    在这个项目中,学生被要求编写一个程序,该程序能够为用户提供杭电校园内从一个景点到另一个景点的最短路径咨询服务。以下是这个报告中的关键知识点: 1. **图的抽象数据类型 (ADT Graph)**: 在需求分析中,首先...

    杭电acm题目解答

    而基础图论问题可能包括最短路径、最小生成树等。 2046题可能更倾向于数据结构的运用,比如二叉树、链表、堆、队列或栈等。这些数据结构在解决实际问题时有着广泛的应用,例如在搜索、排序、优先级队列等方面。 ...

    杭电ACM训练课件

    4. **图论**:讲解最短路径、最小生成树、网络流等图论问题及其对应的算法,如Dijkstra、Floyd、Prim、Kruskal、Ford-Fulkerson等。 5. **数学应用**:介绍组合数学、数论、几何等在编程中的应用,帮助解决一些需要...

    杭电ACM题目1002 1003 1005 1008。。等

    而图论则研究如何在图模型中寻找路径、循环和其他结构,常用于解决网络流量、最短路径等问题。 1005题可能是关于字符串处理或模式匹配的题目。字符串处理涉及到字符数组的操作,包括查找、替换、反转和模式匹配。...

    杭电1180解题报告 诡异的楼梯

    本题采用广度优先搜索来寻找从起点到终点的最短路径。BFS是一种图遍历算法,它从根节点开始,然后遍历所有相邻节点,再遍历它们的所有相邻节点,以此类推。对于此类寻找最短路径的问题,BFS非常适合。 #### 2. ...

    杭电、浙大、清华等高校ACM模板

    2. 图论算法:如Dijkstra最短路径算法、Floyd-Warshall所有对最短路径、Bellman-Ford负权边检测等,它们是解决复杂网络问题的关键。 3. 动态规划:通过状态转移方程解决最优化问题,如斐波那契数列、背包问题、最长...

    杭电Acm部分答案

    常见的数据结构如数组、链表、栈、队列、树、图等,以及排序算法(快速排序、归并排序、堆排序)、查找算法(二分查找、哈希查找)和图论算法(最短路径、最小生成树)都是解题的关键。 3. **C/C++编程**:虽然主要...

    杭电教程贪心算法课件

    2. 贪心算法的应用实例,如霍夫曼编码、Prim最小生成树算法、Dijkstra最短路径算法等,通过实例帮助学生理解贪心算法的工作原理。 3. 贪心算法的局限性,强调虽然贪心算法在某些问题上表现优秀,但并非所有问题都能...

    杭电离散数学试卷

    - **最短路径问题**:寻找图中两点间最短的路径。 - **最小生成树**:在加权图中找到一棵包含所有顶点且权重最小的树。 - **网络流问题**:研究如何在网络中最大化流量的问题。 ### 五、组合数学 #### 排列与组合 ...

    杭电笔试代码模板参考

    3. **熟悉常用算法**: 熟练运用排序(快速排序、归并排序、堆排序等)、查找(二分查找、哈希查找等)、图论算法(深度优先搜索、广度优先搜索、最小生成树、最短路径等)。 4. **逻辑思维与问题分析能力**: 能够...

    杭电ACM解题报告(C/C++)

    - 图:图论是ACM竞赛中的核心部分,如最短路径(Dijkstra、Floyd)、最小生成树(Prim、Kruskal)等。 2. **排序与搜索算法** - 冒泡排序、插入排序、选择排序:基础排序算法,用于理解排序原理。 - 快速排序、...

    杭电ACM部分题目答案和初学者PPT

    - 这个文档可能是前一个答案文档的补充,可能包含了更多题目或者不同阶段的题目解答,可能涵盖了更多类型的算法和数据结构,比如哈希表、堆、图的最小生成树算法(Prim或Kruskal)、最短路径算法(Dijkstra或Floyd-...

    杭电OJ题目分类

    - **1029**:可能是关于区间覆盖或者最短路径的问题,需要考虑如何使用DP来优化解决方案。 - **1114**:此类题目可能涉及到一维或二维数组的状态转移,比如编辑距离问题。 - **1284**:可能涉及到多个阶段的状态转移...

Global site tag (gtag.js) - Google Analytics