/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=2680
Name : 2680 Choose the best route
Date : Sunday, January 15, 2012
Time Stage : half an hour
Result:
5259194 2012-01-15 10:24:58 Accepted 2680
250MS 4120K 1664 B
C++ pyy
Test Data :
Review :
Dijkstra 模板题~~
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define INF 0x0f0f0f0f
#define MAXN 1002
bool used[MAXN] ;
int n, m, s, w ;
int dist[MAXN], map[MAXN][MAXN] ;
int dijkstra ()
{
int i, j ;
int iMinPath, MinPath ;
memset (used, 0, sizeof (used)) ;
for (i = 1 ; i <= n ; ++i)
dist[i] = map[0][i] ;
for (i = 0 ; i <= n ; ++i)
{
iMinPath = 0 ;
MinPath = INF ;
for (j = 1 ; j <= n ; ++j)
{
if (!used[j] && dist[j] < MinPath)
{
iMinPath = j ;
MinPath = dist[j] ;
}
}
used[iMinPath] = true ;
for (j = 1 ; j <= n ; ++j)
{
if (!used[j] && dist[iMinPath] + map[iMinPath][j] < dist[j])
{
dist[j] = dist[iMinPath] + map[iMinPath][j] ;
}
}
}
if (dist[s] == INF)
return -1 ;
return dist[s] ;
}
int main ()
{
int i, j ;
int x, y, c ;
while (~scanf ("%d%d%d", &n, &m, &s))
{
memset (map, INF,sizeof (map)) ;
for (i = 1 ; i <= m ; ++i)
{
scanf ("%d%d%d", &x, &y, &c) ;
map[x][y] = min (map[x][y], c) ;
}
scanf ("%d", &w) ;
for (i = 1 ; i <= w ; ++i)
{
scanf ("%d", &x) ;
map[0][x] = 0 ; // 站点0 为 Kiki 的家,设家到x 的距离为 0
}
printf ("%d\n", dijkstra ()) ;
}
return 0 ;
}
分享到:
相关推荐
毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统 毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统 毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统 毕设项目...
代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法...
最短路径Dijkstra算法-最短路Dijkstra算法.rar 最短路径Dijkstra算法
1、基于springboot+mysql+Dijkstra算法实现物流优化管理系统源码+项目说明(课程设计).zip 2、该资源包括项目的全部源码,下载可以直接使用! 3、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大...
Dijkstra算法求最短路,利用C++程序设计,希望能对你有所帮助
dijkstra算法,最短路问题Dijkstra算法,网络无负权的最短问题Dijkstra算法
毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统 本资源中的源码都是经过本地编译过可运行的,下载后按照文档配置好环境就可以运行。资源项目的难度比较适中,内容都是经过专业老师审定过的,...
最短路Dijkstra算法 Matlab代码Function部分,通用各种类型网络
标准C的图的实现+BFS和DFS遍历+Dijkstra算法+Prim算法+Kruskal算法实现,纯手写!下载后如有疑问可以私信联系!全部手撸,一键运行,都封装成函数了,易读性很强
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
【老生谈算法】floyd最短路算法Dijkstra最短路算法Matlab程序.doc
基于Pyqt5+Dijkstra算法实现的校园地图导览python源码+项目使用说明.zip 语言:Python 主要依赖包: PyQt5 主要算法: Dijkstra 通过工程文件 - > 在配置好的IDE中运行 main.py - > 或cd 进入工程目录 python -...
图论Dijkstra最短路算法matlab通用程序,有实例。希望对大家有用
图论- 最短路- Dijkstra 算法.rar
最短路问题__Dijkstra(迪杰斯特拉算法).ppt
蚁群算法+Dijkstra算法=二维路径规划,基于蚁群算法的机器人路径规划,matlab源码
蚁群算法+Dijkstra算法=二维路径规划,基于蚁群算法的机器人路径规划,matlab源码.rar