Dijkstra 算法
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1596
Name : 1596 find the safest road
Date : Sunday, January 22, 2012
Time Stage : half an hour
Result:
5286524 2012-01-22 16:22:38 Accepted 1596
1015MS 6632K 1962 B
C++ pyy
Test Data :
Review :
//----------------------------------------------------------------------------*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <queue>
using namespace std ;
#define INF (-1)
#define MAXN 1002
typedef __int64 LL ;
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define MEM(a, v) memset (a, v, sizeof (a))
bool used[MAXN] ;
int n, q ;
double map[MAXN][MAXN], dist[MAXN] ;
double dijkstra (const int beg, const int end)
{
int i, j ;
int iMinPath ;
double MaxSafe ;
MEM (used, 0) ;
for (i = 1 ; i <= n ; ++i)
dist[i] = map[beg][i] ;
for (i = 1 ; i <= n ; ++i)
{
iMinPath = 1 ;
MaxSafe = 0 ;
for (j = 1 ; j <= n ; ++j)
{
if (used[j] || dist[j] == 0)
continue ;
if (dist[j] > MaxSafe)
{
iMinPath = j ;
MaxSafe = dist[j] ;
}
}
used[iMinPath] = 1 ;
for (j = 1 ; j <= n ; ++j)
{
if (used[j] || dist[iMinPath] == 0 || map[iMinPath][j] == 0)
continue ;
if (dist[j] == 0 || dist[j] < dist[iMinPath] * map[iMinPath][j])
dist[j] = dist[iMinPath] * map[iMinPath][j] ;
}
}
return dist[end] ;
}
int main ()
{
int i, j ;
int x, y ;
double ret ;
while (~scanf ("%d", &n))
{
for (i = 1 ; i <= n ; ++i)
for (j = 1 ; j <= n ; ++j)
{
scanf ("%lf", &map[i][j]) ;
}
scanf ("%d", &q) ;
for (i = 1 ; i <= q ; ++i)
{
scanf ("%d%d", &x, &y) ;
ret = dijkstra (x, y) ;
if (ret == 0)
puts ("What a pity!") ;
else
printf ("%.3lf\n", ret) ;
}
}
return 0 ;
}
Floyd 算法
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1596
Name : 1596 find the safest road
Date : Sunday, January 22, 2012
Time Stage : half an hour
Result:
5286856 2012-01-22 19:02:13 Accepted 1596
3484MS 6620K 1456 B
C++ pyy
Test Data :
Review :
//----------------------------------------------------------------------------*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <queue>
using namespace std ;
#define INF (-1)
#define MAXN 1002
typedef __int64 LL ;
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define MEM(a, v) memset (a, v, sizeof (a))
int n, q ;
double map[MAXN][MAXN] ;
void floyd ()
{
int i, j, k ;
double d ;
for (k = 1 ; k <= n ; ++k)
for (i = 1 ; i <= n ; ++i)
for (j = 1 ; j <= n ; ++j)
{
// 像这种数据这么大的题(n<=1000),加多条判断语句都会超时……
// 之前这里就是加了一条判断,结果就超时了……无限TLE
d = map[i][k] * map[k][j] ;
if (map[i][j] < d)
map[i][j] = d ;
}
}
int main ()
{
int i, j ;
int x, y ;
double ret ;
while (~scanf ("%d", &n))
{
for (i = 1 ; i <= n ; ++i)
for (j = 1 ; j <= n ; ++j)
{
scanf ("%lf", &map[i][j]) ;
}
floyd () ;
scanf ("%d", &q) ;
for (i = 1 ; i <= q ; ++i)
{
scanf ("%d%d", &x, &y) ;
ret = map[x][y] ;
if (ret == 0)
puts ("What a pity!") ;
else
printf ("%.3lf\n", ret) ;
}
}
return 0 ;
}
Spfa 算法
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL :
Name :
Date :
Time Stage :
Result:
5287003 2012-01-22 21:15:06 Accepted 1596
1046MS 6656K 1783 B
C++ pyy
Test Data :
Review :
//----------------------------------------------------------------------------*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <queue>
using namespace std ;
#define INF (-1)
#define MAXN 1002
typedef __int64 LL ;
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define MEM(a, v) memset (a, v, sizeof (a))
bool used[MAXN] ;
int n, q ;
double map[MAXN][MAXN], dist[MAXN] ;
double spfa (const int beg, const int end)
{
int i, t ;
double d ;
queue<int> q ;
MEM (used, 0) ;
MEM (dist, 0) ;
q.push (beg) ;
used[beg] = 1 ;
dist[beg] = 1 ; // 记得要初始化出发点为1
while (!q.empty ())
{
t = q.front () ;
q.pop () ;
for (i = 1 ; i <= n ; ++i)
{
d = dist[t] * map[t][i] ;
if (dist[i] < d)
{
dist[i] = d ;
if (!used[i])
{
q.push (i) ;
used[i] = 1 ; // 第一次忘了这个,死循环
}
}
}
used[t] = 0 ;
}
return dist[end] ;
}
int main ()
{
int i, j ;
int x, y ;
double ret ;
while (~scanf ("%d", &n))
{
for (i = 1 ; i <= n ; ++i)
for (j = 1 ; j <= n ; ++j)
{
scanf ("%lf", &map[i][j]) ;
}
scanf ("%d", &q) ;
for (i = 1 ; i <= q ; ++i)
{
scanf ("%d%d", &x, &y) ;
ret = spfa (x, y) ;
if (ret == 0)
puts ("What a pity!") ;
else
printf ("%.3lf\n", ret) ;
}
}
return 0 ;
}
分享到:
相关推荐
基于Pyqt5+Dijkstra算法实现的校园地图导览python源码 基于Pyqt5+Dijkstra算法实现的校园地图导览python源码 基于Pyqt5+Dijkstra算法实现的校园地图导览python源码 基于Pyqt5+Dijkstra算法实现的校园地图导览python...
做ACM最短路问题普遍算法的Floyd-Dijkstra-Spfa板子..
毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统.zip主要针对计算机相关专业的正在做课程设计和期末大作业的学生和需要项目实战练习的学习者。包含全部项目源码、该项目可以直接使用、项目都经过...
基于java+dijkstra算法实现上海地铁换乘线路的查询+源码+实现原理解析,适合毕业设计、课程设计、项目开发。项目源码已经过严格测试,可以放心参考并在此基础上延申使用~ 基于java+dijkstra算法实现上海地铁换乘...
代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法...
【老生谈算法】floyd最短路算法Dijkstra最短路算法Matlab程序.doc
最短路问题Dijkstra Floyd算法学习教案 一、最短路问题 最短路问题是指在一个有向网络中,从一个顶点出发,通过若干条弧,到达另一个顶点,并且使总费用最小的旅行路线。例如,在交通网中,从v1出发,通过这个交通...
本文将深入探讨三个著名的最短路径算法:Floyd算法、Dijkstra算法和SPFA(Shortest Path Faster Algorithm)。这些算法广泛应用于图论和网络分析,特别是在路由选择、物流规划、社交网络分析等场景。 1. **Floyd...
毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统 本资源中的源码都是经过本地编译过可运行的,下载后按照文档配置好环境就可以运行。资源项目的难度比较适中,内容都是经过专业老师审定过的,...
【作品名称】:基于Matlab+Dijkstra和时间窗规划的AGV调度算法 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【项目介绍】:基于...
1、基于springboot+mysql+Dijkstra算法实现物流优化管理系统源码+项目说明(课程设计).zip 2、该资源包括项目的全部源码,下载可以直接使用! 3、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大...
最短路径Dijkstra算法是图论中的一个经典算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出,主要用于解决单源最短路径问题。该算法适用于加权有向或无向图,寻找从起始节点到其他所有节点的最短路径。在实际...
标题中的“最短路径+dijkstra+matlab代码+算法效率测试”揭示了本文将要讨论的是图论中的一个经典算法——Dijkstra算法,并且在MATLAB环境下实现与测试该算法的效率。MATLAB是一款强大的数学计算软件,常用于科学...
这里提到的“路径规划,最短路计算,Dijkstra graphshortestpath floyd程序”涉及到了两个著名的算法:Dijkstra算法和Floyd-Warshall算法,它们都是用于解决图论中的最短路径问题。 Dijkstra算法是由荷兰计算机科学...
AGV调度_基于Matlab+Dijkstra算法+时间窗规划实现的AGV调度算法_附项目源码_优质项目实战
基于Pyqt5+Dijkstra算法实现的校园地图导览python源码+项目使用说明.zip 语言:Python 主要依赖包: PyQt5 主要算法: Dijkstra 通过工程文件 - > 在配置好的IDE中运行 main.py - > 或cd 进入工程目录 python -...
dijkstra算法,最短路问题Dijkstra算法,网络无负权的最短问题Dijkstra算法