题解【AcWing176】装满的油箱

一开始拿到这个问题并不好做，于是考虑拆点。

考虑将一个点拆成 \(c+1\) 个，每个点表示（编号，剩余油量）。

然后 \(\text{Dijkstra}\) 最短路即可。

每次跑 \(\text{Dijkstra}\) 时，先判断能不能再加 \(1\) 单位的油，然后遍历每一条出边，加入优先队列。

注意节点编号从 \(0\) 开始。

#include <bits/stdc++.h>

#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)

#define itn int

#define gI gi

using namespace std;

inline int gi()

{

	int f = 1, x = 0; char c = getchar();

	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return f * x;

}

const int maxn = 1003, maxm = 10003, maxx = 103;

int q, n, m, c, s, e, yj[maxn];

int tot, head[maxn], ver[maxm * 2], nxt[maxm * 2], edge[maxm * 2];

int dist[maxn][maxx];

struct Node

{

	int sy, now, y;

	bool operator < (const Node &a) const

	{

		return sy > a.sy;

	}

} ;

inline void add(int u, int v, int w)

{

	ver[++tot] = v, nxt[tot] = head[u], edge[tot] = w, head[u] = tot;

}

int vis[maxn][maxx];

inline int Dij(int c, int s, int e)

{

	priority_queue <Node> q;

	memset(vis, 0, sizeof(vis));

	memset(dist, 0x3f, sizeof(dist));

	q.push((Node){0, s, 0});

	while (!q.empty())

	{

		Node now = q.top(); q.pop();

		if (now.now == e) return now.sy;

		if (vis[now.now][now.y]) continue;

		vis[now.now][now.y] = 1;

		if (now.y < c)

		{

			if (dist[now.now][now.y + 1] > now.sy + yj[now.now])

			{

				dist[now.now][now.y + 1] = now.sy + yj[now.now];

				q.push((Node){dist[now.now][now.y + 1], now.now, now.y + 1});

			}

		}

		for (int i = head[now.now]; i; i = nxt[i])

		{

			int v = ver[i], w = edge[i];

			if (now.y >= w)

			{

				if (dist[v][now.y - w] > now.sy)

				{

					dist[v][now.y - w] = now.sy;

					q.push((Node){now.sy, v, now.y - w});

				}

			}

		}

	}

	return -1;

}

int main()

{

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	n = gi(), m = gi();

	for (int i = 0; i < n; i+=1) yj[i] = gi();

	for (int i = 1; i <= m; i+=1)

	{

		int u = gi(), v = gi(), w = gi();

		add(u, v, w), add(v, u, w);

	}

	q = gi();

	while (q--)

	{

		c = gi(), s = gi(), e = gi();

		int t = Dij(c, s, e);

		if (t == -1) puts("impossible");

		else printf("%d\n", t);

	}

	return 0;

}

巴特西

题解【AcWing176】装满的油箱

最新文章

热门文章