建立超级源点,枚举等级,在等级范围内跑dijkstra,注意初始化,
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int g[N][N];
int level[N];
int dist[N];
bool st[N];
int m, n;
int dijkstra(int down, int up)
{
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
dist[0] = 0;
for (int i = 0; i <= n; i++)
{
int t = -1;
for (int j = 0; j <= n; j++)
{
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
st[t] = true;
for (int j = 1; j <= n; j++)
if (level[j] >= down && level[j] <= up)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
return dist[1];
}
int main()
{
cin >> m >> n;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; i++)g[i][i] = 0;
for (int i = 1; i <= n; i++)
{
int price, cnt;
cin >> price >> level[i] >> cnt;
g[0][i] = min(price, g[0][i]);
while (cnt--)
{
int id, w;
cin >> id >> w;
g[id][i] = min(g[id][i], w);
}
}
int res = 0x3f3f3f3f;
for (int i = level[1] - m; i <= level[1]; i++)
res = min(res, dijkstra(i, i + m));
cout << res << endl;
return 0;
}