【分层最短路】Magical Girl Haze

https://nanti.jisuanke.com/t/31001

有K次机会可以让一条边的权值变为0，求最短路。

在存储单源最短路的数组上多开一维状态，d[i][k]表示走到序号i的点，且让k条边权值为0时的最短路。

对于每个待更新的点，尝试不置零此边的状态和置零此边的状态，分别压入优先队列去更新其他状态。

另外，此题由于有重边，需要先去重，保留同起始点最短的边。

代码：

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstring>

#include <vector>

#include <cstdio>

using namespace std;

typedef long long ll;

const ll INF = 0x3f3f3f3f3f3f3f3fLL;

const int MAX_V = 100005;

const int MAX_E = 200005;

int N, M, K;

struct Dijkstra {

	struct Edge {

		int to, cost, next;

	} es[MAX_E];

	struct Node {

		int u, k;

		ll d;

		Node(int u, ll d, int k) : u(u), d(d), k(k) {}

		bool operator< (const Node& n) const {

			return d > n.d;

		}

	};

	int head[MAX_V];

	int V, E;

	ll d[MAX_V][15];

	bool vis[MAX_V][15];

	void init(int V) {

		this->V = V;

		this->E = 0;

		memset(head, -1, sizeof head);

	}

	void addEdge(int u, int v, int w) {

		es[E].to = v;

		es[E].cost = w;

		es[E].next = head[u];

		head[u] = E++;

	}

	void dijkstra(int s) {

		priority_queue <Node> Q;

		memset(d, 0x3f, sizeof d);

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

		d[s][0] = 0;

		Q.push(Node(s, 0, 0));

		while (!Q.empty()) {

			int u = Q.top().u, k = Q.top().k;

			Q.pop();

			if (vis[u][k])

				continue;

			vis[u][k] = true;

			for (int i = head[u]; i != -1; i = es[i].next) {

				int v = es[i].to, w = es[i].cost;

				if (d[v][k] > d[u][k] + w) {

					d[v][k] = d[u][k] + w;

					Q.push(Node(v, d[v][k], k));

				}

				if (k + 1 <= K) {

					if (d[v][k + 1] > d[u][k]) {

						d[v][k + 1] = d[u][k];

						Q.push(Node(v, d[v][k + 1], k + 1));

					}

				}

			}

		}

	}

} dijk;

struct Elem {

	int u, v, w;

	bool operator< (const Elem& e) const {

		if (u == e.u && v == e.v) {

			return w < e.w;

		}

		if (u == e.u) {

			return v < e.v;

		}

		return u < e.u;

	}

} e[MAX_E];

int main() {

	int T;

	scanf("%d", &T);

	while (T--) {

		scanf("%d%d%d", &N, &M, &K);

		dijk.init(N);

		for (int i = 0; i < M; i++) {

			scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

		}

		sort(e, e + M);

		int preu = 0, prev = 0;

		for (int i = 0; i < M; i++) {

			if (preu != e[i].u || prev != e[i].v) {

				dijk.addEdge(e[i].u, e[i].v, e[i].w);

				preu = e[i].u, prev = e[i].v;

			}

		}

		dijk.dijkstra(1);

		ll ans = INF;

		for (int i = 0; i <= K; i++) {

			ans = min(ans, dijk.d[N][i]);

		}

		printf("%lld\n", ans);

	}

}

巴特西

【分层最短路】Magical Girl Haze

最新文章

热门文章