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
| #include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 1e3 + 50;
int n, m, C, S, E, tot = -1, p[maxn], d[maxn][maxn], head[maxn];
bool vis[maxn][maxn];
struct edge {
int v_, w_, nxt_;
} e[(int)1e4 << 1];
struct node {
int d_, city_, fuel_;
node(int d = 0, int city = 0, int fuel = 0)
: d_(d), city_(city), fuel_(fuel) {}
bool operator<(const node &x) const {
return d_ > x.d_ || (d_ == x.d_ && city_ > x.city_) ||
(d_ == x.d_ && city_ == x.city_ && fuel_ > x.fuel_);
}
};
priority_queue<node> q;
void add(int u, int v, int w) {
e[++tot].v_ = v, e[tot].w_ = w, e[tot].nxt_ = head[u];
head[u] = tot;
}
void dijkstra() {
while (!q.empty()) q.pop();
memset(d, 0x3f, sizeof(d)), memset(vis, 0, sizeof(vis));
d[S][0] = 0;
q.push(node(0, S, 0));
while (!q.empty()) {
node u = q.top();
q.pop();
int city = u.city_, fuel = u.fuel_;
if (vis[city][fuel]) continue;
vis[city][fuel] = 1;
if (u.city_ == E) {
cout << d[city][fuel] << endl;
return;
}
if (fuel < C && d[city][fuel + 1] > d[city][fuel] + p[city]) {
d[city][fuel + 1] = d[city][fuel] + p[city];
q.push(node(d[city][fuel] + p[city], city, fuel + 1));
}
for (int i = head[city]; ~i; i = e[i].nxt_) {
int nxt = e[i].v_, w = e[i].w_;
if (fuel >= w && d[nxt][fuel - w] > d[city][fuel]) {
d[nxt][fuel - w] = d[city][fuel];
q.push(node(d[city][fuel], nxt, fuel - w));
}
}
}
cout << "impossible" << endl;
}
int main() {
cin >> n >> m;
int u, v, w, t;
for (int i = 0; i < n; ++i) cin >> p[i];
memset(head, -1, sizeof(head));
for (int i = 0; i < m; ++i) {
cin >> u >> v >> w;
add(u, v, w), add(v, u, w);
}
cin >> t;
while (t--) {
cin >> C >> S >> E;
dijkstra();
}
return 0;
}
|