当前位置：首页 > news >正文

网站建设一条龙ue365企业文化标语

news 2025/8/4 1:31:17

网站建设一条龙ue365,企业文化标语,教务系统学生登录入口,简单网页制作html题目： Description 经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居…

题目：

Description

经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。

Input

输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。

Output

如果徐总能到达目的地，输出最短的时间；否则，输出“-1”。

Sample Input

6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1

Sample Output

50Hint:
The best route is:
xiasha->ShoppingCenterofHangZhou->supermarket->westlake虽然偶尔会迷路，但是因为有了你的帮助
**和**从此还是过上了幸福的生活。――全剧终――

题意：就是求某点到某点的单源最短路。题意很简单，但是字符串这需要处理一下，因为我没有用hash，所以处理起来就比较麻烦，在字符串复制和查找这出现了一些RE错误，找了半天也是醉了。

实现:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;const int MAX = 200;
const int len = 35;
const int INF = 0x3f3f3f3f;
char s[MAX][len];struct node {int v, key;bool friend operator < (node n1, node n2) {return n1.key > n2.key;}
}d[MAX];struct gg {int vv, kk;
};
vector <gg> path[MAX];
int n, k;
int ss, ee;int find_loc(char t[]) {for (int i = 0; i < k; i++) {if (strcmp(t, s[i]) == 0) {return i;}}int len = strlen(t);for (int i = 0; i < len; i++) {s[k][i] = t[i];}//之前这里用库函数，然后RE到死s[k][len] = '\0';return k++;
}void Dij() {priority_queue <node> q;q.push(d[ss]);while (!q.empty()) {node head = q.top();q.pop();for (int i = 0; i < path[head.v].size(); i++) {if (d[path[head.v][i].vv].key > path[head.v][i].kk + d[head.v].key) {d[path[head.v][i].vv].key = path[head.v][i].kk + d[head.v].key;q.push(d[path[head.v][i].vv]);}}}
}int main() {while (scanf("%d", &n) != EOF) {if (n == -1) {break;}k = 0;for (int i = 0; i < MAX; i++) {path[i].clear();}char start[len];char en[len];scanf("%s", start);scanf("%s", en);char s1[len];char e1[len];int value;for (int i = 0; i < n; i++) {scanf("%s", s1);scanf("%s", e1);scanf("%d", &value);int v1, v2;v1 = find_loc(s1);v2 = find_loc(e1);gg g1, g2;g1.vv = v2;g1.kk = value;g2.vv = v1;g2.kk = value;path[v1].push_back(g1);path[v2].push_back(g2);}ss = find_loc(start);ee = find_loc(en);//注意这里，因为可能出现起点终点相同，没有给路线的情况，或者起点终点不同，没有给样例情况。for (int i = 0; i < k; i++) {d[i].key = INF;d[i].v = i;}d[ss].v = ss;d[ss].key = 0;Dij();if (d[ee].key < INF) {printf("%d\n", d[ee].key);}else {printf("-1\n");}}return 0;
}

样例：

输入：

ss ss

输出：

样例输入：

ss ee

样例输出：

-1

查看全文

http://www.lbrq.cn/news/2569771.html