最短路做法,是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;
}