题目链接
题意:给你n个点, m条边(双向), 每条边有一个编号,求从1到n的最短路。如果没有则输出-1.
规则:经过一条边,花费为1,若经过的下一条边与当前的边编号相同,则下一条边不需要花费, 如果不同则代价+1.
简单来说就是 求 换乘次数+1
例1:
1-2 的编号 为1
1-3 的编号为2
2-3 的编号为1
则最短路 可以是 1-2-3 这里的编号都为1 所以答案为1 也可以是1-3的编号为2 也是代价为1
之前自己写的第一次写法有个很大的错误, 却在比赛中A了, 原因是hdu的数据出的不够严谨, 当时也没多想, 赛后写ac代码, 被评论的数据给hack了, 才知道自己的错误在哪里,菜啊
题解:用优先队列按每个点的最后一条的权值大小进行排序, bfs跑一遍最短路。
正解代码:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85#include<bits/stdc++.h> #define ll long long #define line printf("=============n"); #define inf 0x3f3f3f3f using namespace std; const int maxn = 2e5+5; int head[maxn], tot; int dis[maxn];//记录起点到每个点的最短距离 int n, m; struct edge { int v, id, next;//边的终点 权值 下一条边 } edges[maxn<<2]; void addedge(int u, int v, int id) { //邻接表 edges[++tot] = (edge) { v, id, head[u] }; head[u] = tot; edges[++tot] = (edge) { u, id, head[v] }; head[v] = tot; }//加边 struct node { int id, val, kind;//点的序号 到这个点的权值 到这个点最后一条边的id node() {} node(int _id, int _val, int _kind) : id(_id), val(_val), kind(_kind) {} bool operator < (const node &p) const {//用于优先队列内结构体的排序 return val > p.val; } }; int bfs() { priority_queue<node> q; memset(dis, inf, sizeof(dis)); dis[1] = 0; q.push((node){1, 0, -1}); node temp; while(!q.empty()) { temp = q.top(); q.pop(); if(temp.val > dis[temp.id]) { continue;//当到这个点的权值大于到这个点的最短路 舍去这条路径 } if(temp.id == n) { return temp.val;// 到达终点n直接返回结果 } for(int i = head[temp.id]; i; i = edges[i].next) { //状态比较 进行松弛操作 if(dis[temp.id] + (edges[i].id != temp.kind) < dis[edges[i].v]) { dis[edges[i].v] = dis[temp.id] + (edges[i].id != temp.kind); q.push(node(edges[i].v, dis[edges[i].v], edges[i].id)); } } } return -1; } void init() { tot = 0; memset(head, 0, sizeof(head)); } int main() { while(~scanf("%d%d", &n, &m)){ init(); if(m == 0){ printf("-1n"); }else { for(int i = 0; i < m; i++){ int u, v, id; scanf("%d%d%d", &u,&v,&id); addedge(u,v,id); addedge(v,u,id); } printf("%dn",bfs()); } } return 0; }
最后
以上就是冷静百褶裙最近收集整理的关于hdu6386 Age of Moyu 2018杭电多校第七场A题【优先队列+BFS】(已更改)的全部内容,更多相关hdu6386内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复