题目

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 110, M = 10110;
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
int n, m;
int dist[N];
int tier[N];
void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int Dijkstra(int l, int r)
{memset(dist, 0x3f, sizeof dist);memset(st,0,sizeof st);dist[0] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 0});while(heap.size()){auto t = heap.top(); heap.pop();int u = t.y, distance = t.x;if(st[u]) continue;st[u] = true;for(int k = h[u]; ~k; k = ne[k]){int j = e[k];if(tier[j] < l || tier[j] > r) continue;if(dist[j] > distance + w[k]){dist[j] = distance + w[k];heap.push({dist[j], j});}}}return dist[1];
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> m >> n;memset(h, -1, sizeof h);for(int i = 1; i <= n; i++){int a, b, c;cin >> a >> b >> c;tier[i] = b;add(0, i, a);for(int j = 1; j <= c; j++){int t, v;cin >> t >> v;add(t, i, v);}}int res = INT_MAX;for(int i = tier[1] - m; i <= tier[1]; i++){res = min(res, Dijkstra(i, i+m));}cout << res << endl;return 0;
}

感悟

我建立的图不好实现。下次要灵活一点。

我只考虑到局部的等级，没有想到全局，没有想到枚举区间的做法，更对枚举的范围感到意外

我对边数目的把握有问题，下次要从add函数的出现次数上面分析，这样更加实际