MLE dijkstra求调,玄关
  • 板块P4943 密室
  • 楼主ChampionCyan
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/7 21:33
  • 上次更新2024/5/8 13:00:27
查看原帖
MLE dijkstra求调,玄关
1036180
ChampionCyan楼主2024/5/7 21:33

感觉是dijkstra函数有锅,可能死循环了

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
int n, m, k, ans;
bool go[MAXN], vis[MAXN];

struct edge {
	int v, w;
};

struct node {
	vector < edge > e;
	int u, dis;
	bool operator > (const node& a) const {
		return a.dis > dis;
	}
} g[MAXN];

void dijkstra(bool Harry, int begin) {
	for (int i = 1; i <= n; i++)
		g[i].dis = INT_MAX, vis[i] = false;
	priority_queue < node, vector < node >, greater < node > > q;
	g[begin].dis = 0;
	q.push(g[begin]);
	while (!q.empty()) {
		int u = q.top().u, dis = q.top().dis;
		vector < edge > e = q.top().e;
		q.pop();
		vis[u] = true;
		for (edge ed : e)
			if (!vis[ed.v] && (Harry || !go[ed.v]))
				g[ed.v].dis = dis + ed.w, q.push(g[ed.v]);
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	while (k--) {
		int snake;
		scanf("%d", &snake);
		go[snake] = true;
	}
	while (m--) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[a].e.push_back({ b, c }), g[b].e.push_back({ a, c });
	}
	g[1].dis = 0;
	int x, y;
	scanf("%d%d", &x, &y);
	dijkstra(true, 1);
	int num1 = g[x].dis, num2 = g[y].dis;
	ans = max(num1, num2);
	dijkstra(false, 1);
	ans = min(ans, max(g[y].dis, g[x].dis));
	dijkstra(true, x);
	ans = min(ans, min(num1, num2) + g[y].dis);
	printf("%d", ans);
	return 0;
}
2024/5/7 21:33
加载中...