好贷网好贷款

(step6.2.1)hdu 1690(Bus System——最短路径)

发布时间:2016-12-3 21:55:44 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"(step6.2.1)hdu 1690(Bus System——最短路径)",主要涉及到(step6.2.1)hdu 1690(Bus System——最短路径)方面的内容,对于(step6.2.1)hdu 1690(Bus System——最短路径)感兴趣的同学可以参考一下。

题目大意:输入一个整数t,表示测试用例数。接下来驶入8个整数l1, l2, l3, l4, c1, c2, c3, c4.其中l1~l4表示路程,c1~c4表示费用。路程与费用之间的具体关系 见problem description。接下来输入两个整数n,m。分别表示站(station)的个数以及问题的个数。在接下来的n行中,每行给出一个数,表示各个站的位置 (这里的位置是一维的,所以只给出横坐标)。接下来的m行中,每行给出2个整数start、end,分别表示起始站和终点站。求从起始站到终点站的最小费用 解题思路:最短路径 代码如下: #include <iostream> #include <stdio.h> #include <queue> #include <string.h> #define inf 10000000000000 using namespace std; __int64 map[101][101]; __int64 d[101]; bool hash[101]; __int64 a[101]; __int64 l1, l2, l3, l4, c1, c2, c3, c4; __int64 n, m; __int64 start, end; typedef struct node { __int64 adj;__int64 w; struct node* next; } node, *pnode; /** * 对于c++,一下这种写法也是可以的 * struct node { __int64 adj;__int64 w; struct node* next; } ; */ typedef struct Heap { bool operator<(Heap T) const { return T.dis < dis; } __int64 x;__int64 dis; } Heap; priority_queue<Heap> Q; __int64 bfs() { __int64 i; /** d[i] :从顶点v出发到其余各定点vi可能达到的最短路径 hash[i] : 用来标记顶点i是否被访问过 */ for (i = 0; i <= 100; ++i) { hash[i] = 0; d[i] = inf; } Heap min, in; while (!Q.empty()) { Q.pop(); } in.x = start; in.dis = 0; d[start] = 0; Q.push(in); while (!Q.empty()) { min = Q.top(); Q.pop(); //放在下面会导致超时 if (min.x == end) { return min.dis; } if (hash[min.x]) { continue; } hash[min.x] = true; for (int i = 1; i <= n; ++i) { if (d[i] > map[min.x][i] + d[min.x] && !hash[i]) { in.x = i; in.dis = map[min.x][i] + d[min.x]; d[i] = in.dis; Q.push(in); } } } return -1; } /** 返回距离dis所对应的费用C。 如果没找到对应的费用,则返回-1. */ int judge(int dis) { if (dis > 0 && dis <= l1) { return c1; } else { if (dis > l1 && dis <= l2) { return c2; } else { if (dis > l2 && dis <= l3) { return c3; } else if (dis > l3 && dis <= l4) { return c4; } else { return -1; } } } } int main() { __int64 p = 1, i, j; int t; scanf("%d", &t); //别漏了&t的取地址符号& while (t--) { /** %I64d :用来读取一个__int64的数据 l1、l2、l3、l4 :距离 c1、c2、c3、c4 :费用 mp[i][j] :用来表示顶点i、顶点j之间的权值。不连通时为inf(或者可以理解为无穷大) a[i] : 表示第i个顶点的位置(坐标) n :站的个数 m :问题数 */ scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d", &l1, &l2, &l3, &l4, &c1, &c2, &c3, &c4); scanf("%I64d%I64d", &n, &m); for (i = 0; i <= n; i++) { for (j = 0; j <= n; j++) { map[i][j] = inf; } } for (i = 1; i <= n; i++) { scanf("%I64d", &a[i]); } for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { __int64 l = a[i] - a[j]; if (l < 0) { l = -l;//注意这里是-l而不是负一 } __int64 s = judge(l); if (s < 0) { s = inf; } map[i][j] = s; map[j][i] = s; } } printf("Case %I64d:\n", p++);//这里的%I64d写成%d也是可以的 for (i = 0; i < m; i++) { /** start :用来记录开始位置 end :结束位置 */ scanf("%I64d%I64d", &start, &end); bfs(); if (d[end] == inf) { printf("Station %I64d and station %I64d are not attainable.\n", start, end); } else { printf( "The minimum cost between station %I64d and station %I64d is %I64d.\n", start, end, d[end]); } } } return 0; }

上一篇:Java基础完整笔记
下一篇:xp自动关机命令

相关文章

相关评论