- 浏览: 221026 次
- 性别:
- 来自: 广州
文章分类
最新评论
-
higkoo:
Keepalived在Reload的时候都会提示:Jan 24 ...
open 创建文件并读写的错误--bad file descriptor -
panyanyany:
iminto 写道你忽悠人呢。。。 serial, 明明是po ...
通过 Zend_Db 向 mysql 写入 null 值的问题 -
iminto:
你忽悠人呢。。。 serial, 明明是postgre SQL ...
通过 Zend_Db 向 mysql 写入 null 值的问题 -
基德KID.1412:
y神写得如此的美啊,太特么好勒!特此顶上! ----KIDx
杭电 hdu 1394 Minimum Inversion Number 【线段树 + 详细注释 + 有难度】 -
基德KID.1412:
顶y哥!
【最短路+bfs+剪枝】杭电 hdu 2433 Travel
Floyd 算法
/* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1690 Name : 1690 Bus System Date : Saturday, January 21, 2012 Time Stage : 7 hours Result: 5283668 2012-01-21 17:27:37 Accepted 1690 78MS 288K 2952 B C++ pyy Test Data : Review : 一共WA25次,不仅题意坑爹,数据也很坑爹,总结,这是一个坑爹的世界…… 本题的路径之和貌似是无限接近 0x7fff,ffff,ffff,ffff 的,所以无穷大已经不保险了, 直接 -1 才是正道啊! 感谢华神的指点! //----------------------------------------------------------------------------*/ #include <cstdio> #include <cstring> #include <queue> #include <cstdlib> using namespace std ; #define INF (-1) #define MAXN 102 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, m ; int L[4], C[4], id[MAXN] ; LL map[MAXN][MAXN] ; void floyd () { int i, j, k ; for (k = 1 ; k <= n ; ++k) for (i = 1 ; i <= n ; ++i) for (j = 1 ; j <= n ; ++j) if (map[i][k] != INF && map[k][j] != INF) { if (map[i][j] == INF || map[i][j] > map[i][k] + map[k][j]) map[i][j] = map[i][k] + map[k][j] ; } } // 这个已经没用了 int getid (int x) { int i ; for (i = 1 ; i <= n ; ++i) if (id[i] == x) return i ; return 0 ; } int getdist (int i, int j) { int tmp = id[i] - id[j] ; if (tmp < 0) tmp = -tmp ; if (0 < tmp && tmp <= L[0]) return C[0] ; if (L[0] < tmp && tmp <= L[1]) return C[1] ; if (L[1] < tmp && tmp <= L[2]) return C[2] ; if (L[2] < tmp && tmp <= L[3]) return C[3] ; return INF ; } void makemap () { int i, j ; MEM (map, INF) ; for (i = 1 ; i <= n ; ++i) { for (j = i + 1 ; j <= n ; ++j) { map[i][j] = map[j][i] = getdist (i, j) ; } } } int main () { int i, j, k ; int x, y, tcase ; LL ret ; scanf ("%d", &tcase) ; { k = 0 ; while (k++ < tcase) { for (i = 0 ; i < 4 ; ++i) { scanf ("%d", &L[i]) ; } for (i = 0 ; i < 4 ; ++i) { scanf ("%d", &C[i]) ; } scanf ("%d%d", &n, &m) ; for (i = 1 ; i <= n ; ++i) { scanf ("%d", &id[i]) ; } makemap () ; floyd () ; printf ("Case %d:\n", k) ; for (i = 0 ; i < m ; ++i) { // 这里输入的数字,直接就是下标了,不用 getid() 了 // 一直以为 x,y 有可能是 -10000…… 到 10000…… scanf ("%d%d", &x, &y) ; ret = map[x][y] ; if (ret == INF) printf ("Station %d and station %d are not attainable.\n", x, y) ; else printf ( "The minimum cost between station %d and station %d is %I64d.\n", x, y, ret) ; } } } return 0 ; }
Spfa 算法
/* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1690 Name : 1690 Bus System Date : Saturday, January 21, 2012 Time Stage : 7 hours Result: 5283757 2012-01-21 18:08:50 Accepted 1690 234MS 304K 3430 B C++ pyy Test Data : Review : 本题的路径之和貌似是无限接近 0x7fff,ffff,ffff,ffff 的,所以无穷大已经不保险了, 直接 -1 才是正道啊! 感谢华神的指点! //----------------------------------------------------------------------------*/ #include <cstdio> #include <cstring> #include <queue> #include <cstdlib> using namespace std ; #define INF (-1) #define MAXN 102 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, m ; int L[4], C[4], id[MAXN] ; LL dist[MAXN], map[MAXN][MAXN] ; LL spfa (const int beg, const int end) { int i, t ; queue<int> q ; MEM (used, 0) ; MEM (dist, INF) ; q.push (beg) ; used[beg] = 1 ; dist[beg] = 0 ; while (!q.empty ()) { t = q.front () ; q.pop () ; for (i = 1 ; i <= n ; ++i) { if (dist[t] == INF || map[t][i] == INF) continue ; if (dist[i] == INF || dist[i] > dist[t] + map[t][i]) { dist[i] = dist[t] + map[t][i] ; if (!used[i]) { used[i] = 1 ; q.push (i) ; } } } used[t] = 0 ; } return dist[end] ; } // 这个已经没用了 int getid (int x) { int i ; for (i = 1 ; i <= n ; ++i) if (id[i] == x) return i ; return 0 ; } int getdist (int i, int j) { int tmp = id[i] - id[j] ; if (tmp < 0) tmp = -tmp ; if (0 < tmp && tmp <= L[0]) return C[0] ; if (L[0] < tmp && tmp <= L[1]) return C[1] ; if (L[1] < tmp && tmp <= L[2]) return C[2] ; if (L[2] < tmp && tmp <= L[3]) return C[3] ; return INF ; } void makemap () { int i, j ; MEM (map, INF) ; for (i = 1 ; i <= n ; ++i) { for (j = i + 1 ; j <= n ; ++j) { map[i][j] = map[j][i] = getdist (i, j) ; } } } int main () { int i, k ; int x, y, tcase ; LL ret ; scanf ("%d", &tcase) ; { k = 0 ; while (k++ < tcase) { for (i = 0 ; i < 4 ; ++i) { scanf ("%d", &L[i]) ; } for (i = 0 ; i < 4 ; ++i) { scanf ("%d", &C[i]) ; } scanf ("%d%d", &n, &m) ; for (i = 1 ; i <= n ; ++i) { scanf ("%d", &id[i]) ; } makemap () ; printf ("Case %d:\n", k) ; for (i = 0 ; i < m ; ++i) { // 这里输入的数字,直接就是下标了,不用 getid() 了 // 一直以为 x,y 有可能是 -10000…… 到 10000…… scanf ("%d%d", &x, &y) ; ret = spfa (x, y) ; if (ret == INF) printf ("Station %d and station %d are not attainable.\n", x, y) ; else printf ( "The minimum cost between station %d and station %d is %I64d.\n", x, y, ret) ; } } } return 0 ; }
Dijkstra 算法
/* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1690 Name : 1690 Bus System Date : Saturday, January 21, 2012 Time Stage : 7 hours Result: 5283728 2012-01-21 17:54:39 Accepted 1690 468MS 292K 3628 B C++ pyy Test Data : Review : 因为一张图要反复利用,所以 Floyd 会比 Dijkstra 快 本题的路径之和貌似是无限接近 0x7fff,ffff,ffff,ffff 的,所以无穷大已经不保险了, 直接 -1 才是正道啊! 感谢华神的指点! //----------------------------------------------------------------------------*/ #include <cstdio> #include <cstring> #include <queue> #include <cstdlib> using namespace std ; #define INF (-1) #define MAXN 102 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, m ; int L[4], C[4], id[MAXN] ; LL dist[MAXN], map[MAXN][MAXN] ; LL dijkstra (const int beg, const int end) { int i, j ; int iMinPath ; LL MinPath ; MEM (used, 0) ; for (i = 1 ; i <= n ; ++i) dist[i] = map[beg][i] ; for (i = 1 ; i <= n ; ++i) { iMinPath = 0 ; MinPath = INF ; for (j = 1 ; j <= n ; ++j) { if (used[j] || dist[j] == INF) continue ; if (MinPath == INF || dist[j] < MinPath) { iMinPath = j ; MinPath = dist[j] ; } } used[iMinPath] = 1 ; for (j = 1 ; j <= n ; ++j) { if (used[j]) continue ; if (dist[iMinPath] == INF || map[iMinPath][j] == INF) continue ; if (dist[j] == INF || dist[iMinPath] + map[iMinPath][j] < dist[j]) dist[j] = dist[iMinPath] + map[iMinPath][j] ; } } return dist[end] ; } // 这个已经没用了 int getid (int x) { int i ; for (i = 1 ; i <= n ; ++i) if (id[i] == x) return i ; return 0 ; } int getdist (int i, int j) { int tmp = id[i] - id[j] ; if (tmp < 0) tmp = -tmp ; if (0 < tmp && tmp <= L[0]) return C[0] ; if (L[0] < tmp && tmp <= L[1]) return C[1] ; if (L[1] < tmp && tmp <= L[2]) return C[2] ; if (L[2] < tmp && tmp <= L[3]) return C[3] ; return INF ; } void makemap () { int i, j ; MEM (map, INF) ; for (i = 1 ; i <= n ; ++i) { for (j = i + 1 ; j <= n ; ++j) { map[i][j] = map[j][i] = getdist (i, j) ; } } } int main () { int i, k ; int x, y, tcase ; LL ret ; scanf ("%d", &tcase) ; { k = 0 ; while (k++ < tcase) { for (i = 0 ; i < 4 ; ++i) { scanf ("%d", &L[i]) ; } for (i = 0 ; i < 4 ; ++i) { scanf ("%d", &C[i]) ; } scanf ("%d%d", &n, &m) ; for (i = 1 ; i <= n ; ++i) { scanf ("%d", &id[i]) ; } makemap () ; printf ("Case %d:\n", k) ; for (i = 0 ; i < m ; ++i) { // 这里输入的数字,直接就是下标了,不用 getid() 了 // 一直以为 x,y 有可能是 -10000…… 到 10000…… scanf ("%d%d", &x, &y) ; ret = dijkstra (x, y) ; if (ret == INF) printf ("Station %d and station %d are not attainable.\n", x, y) ; else printf ( "The minimum cost between station %d and station %d is %I64d.\n", x, y, ret) ; } } } return 0 ; }
发表评论
-
【最短路+bfs+剪枝】杭电 hdu 2433 Travel
2012-01-25 14:44 1741/* THE PROGRAM IS MADE BY ... -
【最短路+spfa+有难度】杭电 hdu 2377 Bus Pass
2012-01-24 15:20 1200/* THE PROGRAM IS MADE BY ... -
【最短路+dijkstra+floyd+spfa】1596 find the safest road
2012-01-22 21:39 1153Dijkstra 算法 /* THE PROGRAM ... -
【最短路+dijkstra+spfa】杭电 hdu 2722 Here We Go(relians) Again
2012-01-20 23:59 1232Dijkstra 解法 /* THE PROGR ... -
【最短路+dijkstra+spfa】杭电 hdu 2962 Trucking
2012-01-19 18:39 1059Spfa 解法 /* THE PROGRAM I ... -
【最短路+dijkstra】杭电 hdu 2923 Einbahnstrasse
2012-01-18 20:24 1224/* THE PROGRAM IS MADE BY PY ... -
【最短路+dijkstra+有难度】杭电 hdu 1245 Saving James Bond
2012-01-17 16:51 1200/* THE PROGRAM IS MADE BY ... -
【最短路+dijkstra】 2680 Choose the best route
2012-01-15 10:30 1103/* THE PROGRAM IS MADE BY ... -
【最短路+floyd】杭电 hdu 1217 Arbitrage
2012-01-15 09:55 1086/* THE PROGRAM IS MADE BY ... -
【最短路+dfs+dijkstra】杭电 hdu 1142 A Walk Through the Forest
2012-01-13 16:31 1424/* THE PROGRAM IS MADE BY PY ... -
【最短路+模板题】杭电 hdu 2112 HDU Today
2012-01-13 10:15 1611/* THE PROGRAM IS MADE BY PY ... -
【图论之最短路】杭电 hdu 2544 最短路
2012-01-05 17:54 1853Dijkstra 算法 /* T ... -
杭电 hdu 1548 A strange lift
2011-08-25 19:51 1600/* THE PROGRAM IS MADE BY PYY ... -
杭电 hdu 1874 畅通工程续
2011-08-19 21:52 1150第二次 /* THE PROGRAM IS MADE BY ... -
杭电 hdu 2066 一个人的旅行
2011-08-19 20:52 1086第二次 /* THE PROGRAM IS MADE B ...
相关推荐
《杭电HDU ACM培训课件》是一份珍贵的学习资源,源自杭州电子科技大学的ACM竞赛培训课程。这些课件是官方论坛上分享的,旨在为那些积分不足无法获取资源或者对ACM编程竞赛感兴趣的初学者提供帮助。下面将详细阐述这...
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
计算机网络复习大纲_杭电hdu.pdf
计算机网络复习大纲_杭电hdu整理.pdf
计算机网络复习大纲_杭电hdu参考.pdf
杭电ACM1005题源代码,AC了的程序,无问题……
杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
杭电hdu acm资料所用杭电的acm题
物理层是网络的最底层,负责数据的物理传输,包括单工、半双工和全双工三种方式。模拟信号和数字信号是电信号的两种形式,模拟信号连续变化,数字信号以离散电平代表0和1。 总结以上,本复习大纲全面覆盖了计算机...
这份"HDU杭电 计算机网络实验报告"压缩包提供了丰富的实验材料,涵盖了多个关键的网络技术,包括交换机配置、路由协议、地址转换(NAT)、访问控制列表(ACL)以及动态主机配置协议(DHCP)等。以下是这些实验报告所...
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字
"acm课件搜索(杭电)(HDU)"这个主题聚集了相关的学习材料,特别是针对搜索算法的讲解,旨在帮助学生快速掌握并应用这些技术。 搜索算法在ACM竞赛中扮演着至关重要的角色,常见的搜索策略包括深度优先搜索(DFS)...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC)中,数学是至关重要的一部分,尤其是在解决杭电(Hangzhou Dianzi University,简称HDU)的题目时。本课件"acm课件简单...