[AHOI2002]哈利·波特与魔法石

125 阅读 0 评论 83 点赞

我是靠谱客的博主强健小懒猪，最近开发中收集的这篇文章主要介绍[AHOI2002]哈利·波特与魔法石，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这道题比较简单，就是一个最短路（SSSP）。数据水，用Floyd即可AC。这里用了Dijkstra。


1 #include <iostream>

2 #include <cstdio>

3 #include <cstring>

4 #include <algorithm>

5 #include <queue>

6

7 using namespace std;

8

9 #define re register
 10 #define rep(i, a, b) for (re int i = a; i <= b; ++i)
 11 #define repd(i, a, b) for (re int i = a; i >= b; --i)
 12 #define maxx(a, b) a = max(a, b);
 13 #define minn(a, b) a = min(a, b);
 14 #define LL long long
 15 #define inf (1 << 30)
 16
 17 inline int read() {
 18
int w = 0, f = 1; char c = getchar();
 19
while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
 20
while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();
 21
return w * f;
 22 }
 23
 24 const int maxn = 100 + 5, maxm = 1e4 + 5;
 25
 26 struct Edge {
 27
int u, v, w, pre;
 28 };
 29
 30 struct Node {
 31
int u, d;
 32
bool operator < (const Node &rhs) const {
 33
return d > rhs.d;
 34 
}
 35 };
 36
 37 int way[8] = {0, 2, 6, 4, 8, 6, 10, 14};
 38
 39 priority_queue<Node> Q;
 40
 41 struct Graph {
 42 #define iter(i, u) for (re int i = G[u]; i; i = edges[i].pre)
 43
Edge edges[maxm << 1];
 44
int n, m;
 45
int G[maxn];
 46
int dis[maxn], vis[maxn];
 47
void init(int n) {
 48
this->n = n;
 49
m = 0;
 50
memset(G, 0, sizeof(G));
 51 
}
 52
void AddEdge(int u, int v, int w) {
 53
edges[++m] = (Edge){u, v, way[w], G[u]};
 54
G[u] = m;
 55
edges[++m] = (Edge){v, u, way[w], G[v]};
 56
G[v] = m;
 57 
}
 58
void dijkstra(int s) {
 59
memset(vis, 0, sizeof(vis));
 60
memset(dis, 0x3f, sizeof(dis));
 61
dis[s] = 0;
 62
Q.push((Node){s, 0});
 63
while (!Q.empty()) {
 64
int u = Q.top().u; Q.pop();
 65
if (vis[u]) continue;
 66
vis[u] = 1;
 67 
iter(i, u) {
 68
Edge &e = edges[i];
 69
if (dis[u] + e.w < dis[e.v]) {
 70
dis[e.v] = dis[u] + e.w;
 71 
Q.push((Node){e.v, dis[e.v]});
 72 
}
 73 
}
 74 
}
 75 
}
 76 } G;
 77
 78 int s, t, m;
 79
 80 int main() {
 81
freopen("ques.in", "r", stdin);
 82
freopen("ques.out", "w", stdout);
 83
 84
rep(i, 1, 7)
 85
if (read()) way[i] >>= 1;
 86
 87
s = read(), t = read();
 88
 89
G.init(100);
 90
 91
m = read();
 92
 93
rep(i, 1, m) {
 94
int u = read(), v = read(), w = read();
 95 
G.AddEdge(u, v, w);
 96 
}
 97
 98 
G.dijkstra(s);
 99
100
printf("%d", G.dis[t]);
101
102
return 0;
103 }

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>
using namespace std;
#define re register#define rep(i, a, b) for (re int i = a; i <= b; ++i)#define repd(i, a, b) for (re int i = a; i >= b; --i)#define maxx(a, b) a = max(a, b);#define minn(a, b) a = min(a, b);#define LL long long#define inf (1 << 30)
inline int read() {int w = 0, f = 1; char c = getchar();while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();return w * f;}
const int maxn = 100 + 5, maxm = 1e4 + 5;
struct Edge {int u, v, w, pre;};
struct Node {int u, d;bool operator < (const Node &rhs) const {return d > rhs.d;}};
int way[8] = {0, 2, 6, 4, 8, 6, 10, 14};

priority_queue<Node> Q;
struct Graph {#define iter(i, u) for (re int i = G[u]; i; i = edges[i].pre)Edge edges[maxm << 1];int n, m;int G[maxn];int dis[maxn], vis[maxn];void init(int n) {this->n = n;m = 0;memset(G, 0, sizeof(G));}void AddEdge(int u, int v, int w) {edges[++m] = (Edge){u, v, way[w], G[u]};G[u] = m;edges[++m] = (Edge){v, u, way[w], G[v]};G[v] = m;}void dijkstra(int s) {memset(vis, 0, sizeof(vis));memset(dis, 0x3f, sizeof(dis));dis[s] = 0;Q.push((Node){s, 0});while (!Q.empty()) {int u = Q.top().u; Q.pop();if (vis[u]) continue;vis[u] = 1;iter(i, u) {Edge &e = edges[i];if (dis[u] + e.w < dis[e.v]) {dis[e.v] = dis[u] + e.w;Q.push((Node){e.v, dis[e.v]});}}}}} G;
int s, t, m;
int main() {freopen("ques.in", "r", stdin);freopen("ques.out", "w", stdout);
rep(i, 1, 7) if (read()) way[i] >>= 1;
s = read(), t = read();
G.init(100);
m = read();
rep(i, 1, m) {int u = read(), v = read(), w = read();G.AddEdge(u, v, w);}
G.dijkstra(s);
printf("%d", G.dis[t]);
return 0;}