求助ABC E题
  • 板块学术版
  • 楼主rlc202204
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/10/1 21:48
  • 上次更新2023/10/27 09:17:49
查看原帖
求助ABC E题
529794
rlc202204楼主2022/10/1 21:48

我知道不是正解,但我不知道我的代码哪里错了,WA 了三个点,求大佬指点。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
struct Edge {
	int to, num, val;
	vector<int> v;
	Edge (int _to = 0, int _num = 0, int _val = 0) :
		to(_to), num(_num), val(_val) {}
};
struct Node {
	int u, num;
	long long dist;
	Node (int _u = 0, int _num = 0, long long _dist = 0) :
		u(_u), num(_num), dist(_dist) {}
};
bool operator<(Node x, Node y) {
	return x.dist > y.dist;
}
vector<Edge> e[MAXN];
int n, m, k;
int E[MAXN] = {0};
pair<int, int> pos[MAXN];
long long dis[MAXN] = {0};
bool vis[MAXN] = {0};
void Dijkstra(int st) {
	memset(dis, 0x3f, sizeof dis);
	priority_queue<Node> q;
	q.push(Node(st, 0, 0));
	dis[st] = 0;
	while (!q.empty()) {
		int h = q.top().u, nm = q.top().num;
		q.pop();
		if (vis[h])
			continue;
		vis[h] = true;
		for (int i = 0; i < (int)e[h].size(); i++)
			if (!vis[e[h][i].to] && dis[e[h][i].to] > dis[h] + e[h][i].val) {
				for (int j = 0; j < (int)e[h][i].v.size(); j++)
					if (e[h][i].v[j] > nm) {
						dis[e[h][i].to] = dis[h] + e[h][i].val;
						q.push(Node(e[h][i].to, e[h][i].v[j], dis[e[h][i].to]));
						break;
					}
			}
	}
}
int main() {
	cin >> n >> m >> k;
	for (int i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		e[u].push_back(Edge(v, 0, w));
		pos[i] = make_pair(u, (int)e[u].size() - 1);
	}
	for (int i = 1, x; i <= k; i++) {
		cin >> x;
		e[pos[x].first][pos[x].second].v.push_back(i);
	}
	Dijkstra(1);
	if (dis[n] == 4557430888798830399)
		cout << -1;
	else
		cout << dis[n] << endl;
	return 0;
}
2022/10/1 21:48
加载中...