一、内容
题目连接 有N个城市（编号0、1…N-1）和M条道路，构成一张无向图。
在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。
现在你需要回答不超过100个问题，在每个问题中，请计算出一架油箱容量为C的车子，从起点城市S开到终点城市E至少要花多少油钱？ 输入格式
第一行包含两个整数N和M。
第二行包含N个整数，代表N个城市的单位油价，第i个数即为第i个城市的油价pi
。
接下来M行，每行包括三个整数u,v,d，表示城市u与城市v之间存在道路，且车子从u到v需要消耗的油量为d。
接下来一行包含一个整数q，代表问题数量。
接下来q行，每行包含三个整数C、S、E，分别表示车子油箱容量、起点城市S、终点城市E。 输出格式
对于每个问题，输出一个整数，表示所需的最少油钱。
如果无法从起点城市开到终点城市，则输出”impossible”。
每个结果占一行。 数据范围
1≤N≤1000, 1≤M≤10000, 1≤pi≤100, 1≤d≤100, 1≤C≤100
输入样例：
5 5 10 10 20 12 13 0 1 9 0 2 8 1 2 1 1 3 11 2 3 7 2 10 0 3 20 1 4
输出样例：
170 impossible
二、思路
每一次入队有2种操作，第一种是加一升油入队， 第二种是看是否能到达下一个点。求从起点到终点的最少花费，利用最短路的思想， 每次从队里面出来的节点必定是花费最少的， dis[u][c] 代表到达u点还剩c升油的最少花费。 这样当到达终点后，必然是最少花费，直接return即可。
三、代码
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std
;
const int N
= 1e3 + 5, M
= 1e4 + 5, C
= 105;
int n
, m
, price
[N
], vis
[N
][C
], dis
[N
][C
], head
[N
], len
= 1, su
, sv
, w
, code
, c
;
struct E
{
int v
, next
, w
;
} e
[2 * M
];
struct Node
{
int u
, d
, c
;
Node(int uu
, int dd
, int cc
) {
u
= uu
;
d
= dd
;
c
= cc
;
}
friend bool operator <(Node a
, Node b
) {
return a
.d
> b
.d
;
}
};
void add(int u
, int v
, int w
) {
e
[len
].v
= v
;
e
[len
].next
= head
[u
];
e
[len
].w
= w
;
head
[u
] = len
++;
}
int bfs() {
priority_queue
<Node
> q
;
memset(dis
, 0x3f, sizeof(dis
));
memset(vis
, 0, sizeof(vis
));
q
.push(Node(su
, 0, 0));
int u
, tc
;
while (!q
.empty()) {
Node t
= q
.top();
q
.pop();
u
= t
.u
;
tc
= t
.c
;
if (u
== sv
) return t
.d
;
if (vis
[u
][tc
]) continue;
vis
[u
][tc
] = 1;
if (tc
< c
) {
if (dis
[u
][tc
+ 1] > t
.d
+ price
[u
]) {
dis
[u
][tc
+ 1] = t
.d
+ price
[u
];
q
.push(Node(u
, dis
[u
][tc
+ 1], tc
+ 1));
}
}
for (int j
= head
[u
]; j
; j
= e
[j
].next
) {
int v
= e
[j
].v
;
if (tc
>= e
[j
].w
) {
if (dis
[v
][tc
- e
[j
].w
] > t
.d
) {
q
.push(Node(v
, t
.d
, tc
- e
[j
].w
));
}
}
}
}
return -1;
}
int main() {
scanf("%d%d", &n
, &m
);
for (int i
= 0; i
< n
; i
++) {
scanf("%d", price
+ i
);
}
for (int i
= 1; i
<= m
; i
++) {
scanf("%d%d%d", &su
, &sv
, &w
);
add(su
, sv
, w
);
add(sv
, su
, w
);
}
scanf("%d", &code
);
for (int i
= 1; i
<= code
; i
++) {
scanf("%d%d%d", &c
, &su
, &sv
);
int t
= bfs();
if (t
== -1) {
printf("impossible\n");
} else {
printf("%d\n", t
);
}
}
return 0;
}
