/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=2923
Name : 2923 Einbahnstrasse
Date : Wednesday, January 18, 2012
Time Stage : two hours
Result:
5272119 2012-01-18 15:32:10 Accepted 2923
62MS 300K 2686 B
C++ pyy
Test Data :
Review :
一次AC, 太神奇了~~
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string>
#include <map>
#include <utility>
#include <iostream>
using namespace std ;
#define INF 0x3f3f3f3f
#define MAXN 105
#define min(x, y) ((x) < (y) ? (x) : (y))
#define MEM(a, v) memset (a, v, sizeof (a))
bool used[MAXN] ;
int n, c, r, iCityCnt ;
int graph[MAXN][MAXN], cars[MAXN], from[MAXN], to[MAXN] ;
void dijkstra (int * dist, bool bfrom)
{
int i, j ;
int iMinPath, MinPath ;
MEM(used, 0) ;
for (i = 1 ; i <= n ; ++i)
{
dist[i] = (bfrom ? graph[1][i] : graph[i][1]) ;
}
for (i = 1 ; 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] = 1 ;
for (j = 1 ; j <= n ; ++j)
if (!used[j])
dist[j] = min (dist[j], dist[iMinPath] +
(bfrom ? graph[iMinPath][j] : graph[j][iMinPath])) ;
}
}
template <typename T>
void addCity (T &cnr, string city)
{
pair<typename T::iterator, bool> ret ;
ret = cnr.insert (pair<string, int> (city, iCityCnt)) ;
iCityCnt += (ret.second ? 1 : 0) ; //
}
int main ()
{
int i, j, k ;
int v, sum, tcase ;
string str ;
char stra[20], strb[20], ca, cb ;
tcase = 0 ;
while (scanf ("%d%d%d", &n, &c, &r), n | c | r)
{
MEM(graph, INF) ;
MEM(cars, 0) ;
map<string, int> id ;
// number each location
for (i = iCityCnt = 1 ; i <= c + 1 ; ++i)
{
cin >> str ;
// 各点的处理比较别扭,因为它们不是一次性给出的,而是分两部分给的
// 第一部分出现在汽车出事的点,这里给出的点仅仅是一部分而已
addCity (id, str) ;
++cars[id[str]] ;
}
for (i = 1 ; i <= r ; ++i)
{
scanf ("%s %c-%d-%c %s", stra, &ca, &v, &cb, strb) ;
// 这里也给出了各点,而且这里给出的才是完整的。但在我的程序里,
// 优先选择前面的点,剩下的点在这里补充
addCity (id, string (stra)) ;
addCity (id, string (strb)) ;
j = id[stra] ;
k = id[strb] ;
// 根据路径的方向给地图加边
if (ca == '<')
graph[k][j] = min (graph[k][j], v) ;
if (cb == '>')
graph[j][k] = min (graph[j][k], v) ;
}
// 因为要求拖车从总站出发,然后把车拖回总站,所以一来一回就有两段路
// 所以第一次 dijkstra 就计算从总站到各点的路径
// 第二次 dijkstra 就计算从各点到总站的路径
dijkstra (from, 1) ;
dijkstra (to, 0) ;
sum = 0 ;
for (i = 2 ; i <= n ; ++i)
{
// 有几辆车,该路就要走几次
if (from[i] < INF)
sum += from[i] * cars[i] ;
if (to[i] < INF)
sum += to[i] * cars[i] ;
}
printf ("%d. %d\n", ++tcase, sum) ;
}
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、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大...
毕设项目:基于springboot+mysql+Dijkstra算法实现物流优化管理系统 本资源中的源码都是经过本地编译过可运行的,下载后按照文档配置好环境就可以运行。资源项目的难度比较适中,内容都是经过专业老师审定过的,...
标准C的图的实现+BFS和DFS遍历+Dijkstra算法+Prim算法+Kruskal算法实现,纯手写!下载后如有疑问可以私信联系!全部手撸,一键运行,都封装成函数了,易读性很强
基于Pyqt5+Dijkstra算法实现的校园地图导览python源码+项目使用说明.zip 语言:Python 主要依赖包: PyQt5 主要算法: Dijkstra 通过工程文件 - > 在配置好的IDE中运行 main.py - > 或cd 进入工程目录 python -...
蚁群算法+Dijkstra算法=二维路径规划,基于蚁群算法的机器人路径规划,matlab源码
蚁群算法+Dijkstra算法=二维路径规划,基于蚁群算法的机器人路径规划,matlab源码.rar
dijkstra算法,最短路问题Dijkstra算法,网络无负权的最短问题Dijkstra算法
【老生谈算法】floyd最短路算法Dijkstra最短路算法Matlab程序.doc
Dijkstra算法求最短路,利用C++程序设计,希望能对你有所帮助
图论- 最短路- Dijkstra 算法.rar
Dijkstra算法可以解决voronoi图中求解最短路径
最短路Dijkstra算法 Matlab代码Function部分,通用各种类型网络
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
最短路问题Dijkstra Floyd 算法PPT学习教案.pptx