HDU 2544 最短路 Dijkstra Flyod

浴室插座最好选防水型，防止短路。 #生活技巧# #家居技巧# #浴室装修设计#

最短路

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 59887    Accepted Submission(s): 26380

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

Source

Recommend

lcy

方法Dijkstra

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

#define INF 0x3f3f3f3;

int map[110][110],dis[110],visited[110];

void Dijkstra(int n,int x)

{

int i,p,j,min;

for(i=1;i<=n;i++)

{

dis[i]=map[1][i];

visited[i]=0;

}

visited[x]=1;

for(i=1;i<=n;i++)

{

min=INF;

for(j=1;j<=n;j++)

{

if(!visited[j]&&dis[j]<min)

{

p=j;

min=dis[j];

}

}

visited[p]=1;

for(j=1;j<=n;j++)

{

if(!visited[j]&&dis[p]+map[p][j]<dis[j])

{

dis[j]=dis[p]+map[p][j];

}

}

}

}

int main()

{

int n,m,i,j,a,b,t;

while(scanf("%d%d",&n,&m)!=EOF,n+m)

{

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

map[i][j]=INF;

}

for(i=1;i<=m;i++)

{

scanf("%d%d%d",&a,&b,&t);

map[a][b]=map[b][a]=t;

}

Dijkstra(n,1);

printf("%d\n",dis[n]);

}

return 0;

}

Flyod

#include <iostream>

#include <cstdio>

using namespace std;

const int INF=0x3f3f3f3f;

int dis[105][105];

int main()

{

int i,j,k,n,m,p,q,s;

while(scanf("%d%d",&n,&m)!=EOF,n+m)

{

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

dis[i][j]=INF;

}

}

for(i=0;i<m;i++)

{

scanf("%d%d%d",&p,&q,&s);

dis[p][q]=dis[q][p]=s;

}

for(k=1;k<=n;k++)

{

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

if(dis[i][j]>dis[i][k]+dis[k][j])

{

dis[i][j]=dis[i][k]+dis[k][j];

}

}

}

}

printf("%d\n",dis[1][n]);

}

return 0;

}

网址：HDU 2544 最短路 Dijkstra Flyod https://www.yuejiaxmz.com/news/view/534793

相关内容

旅游省钱大法：加权最短路径
数模 03图论Dijkstra and Floyd matlab 及 软件使用
揭秘最佳路线算法：如何轻松驾驭复杂交通，节省出行时间？
【拓扑排序】HDU 1285 确定比赛名次
网络优化的算法：从路由到内容分发1.背景介绍 网络优化算法在现实生活中扮演着至关重要的角色，它们主要用于提高网络性能、降
标题：告别繁琐！Python助你轻松规划完美出行路线
无人驾驶车辆路径规划：用数学建模实现自动驾驶的高效导航
Android编程实现智能交通系统：实时路况监测与导航优化
arcpy 最短路径
图论

随便看看