1pts求调
  • 板块P1882 接力赛跑
  • 楼主Sp6kw
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/17 23:02
  • 上次更新2024/7/18 08:56:59
查看原帖
1pts求调
611118
Sp6kw楼主2024/7/17 23:02

最短路做法,是dij错了?

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
using pairii = pair<int, int>;
const int MAXN = 1e3 + 5;

int n, m;
int l[MAXN], dist[MAXN];
bool vis[MAXN];
vector<pairii> edges[MAXN];
priority_queue<pairii, vector<pairii>, greater<pairii>> q;

void dij(int st) {
	dist[st] = 0;
	q.push({0, st});
	while (!q.empty()) {
		pairii u = q.top();
		q.pop();
		if (vis[u.second]) continue;
		vis[u.second] = 1;
		for (auto i : edges[u.second]) {
			if (dist[u.second] > dist[i.second] + i.first) {
				dist[u.second] = dist[i.second] + i.first;
				q.push({ i.first, i.second });
			}
		}

	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> l[i] >> m;
		for (int j = 1; j <= m; j++) {
			int a;
			cin >> a;
			edges[i].push_back({ l[i], a });
		}
	}
	memset(dist, 0x3f, sizeof(dist));
	dij(1);
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dist[i] + l[i]);
	}
	cout << ans;
	return 0;
}
2024/7/17 23:02
加载中...