Link

大概思路是超级源点，然后枚举交易等级区间。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 5, INF = 1e18;
int n, d[N], p[N], v[N], l[N], a, ans = INF;
vector<pair<int, int>> g[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
bool in(int k, int mn, int mx) {
    return k >= mn && k <= mx;
}
void Dijkstra(int s, int mn, int mx) {
    while(!q.empty()) q.pop();
    for(int i = 0; i <= n; i++) d[i] = INF, p[i] = -1, v[i] = 0;
    d[s] = 0;
    q.push({d[s], s});
    while(!q.empty()) {
        int i = q.top().second;
        q.pop();
        if(v[i] || (i && !in(l[i], mn, mx))) continue;
        v[i] = 1;
        for(auto j : g[i]) {
            int k = j.first, w = j.second;
            if(d[k] > d[i] + w) {
                d[k] = d[i] + w, p[k] = i;
                q.push({d[k], k});
            }
        }
    }
}
void make(int u, int v, int w) {
    g[u].push_back({v, w});
}
signed main() {
    cin>>a>>n;
    for(int i = 1; i <= n; i++) {
        int x, y, z; cin>>x>>y>>z;
        make(0, i, x); l[i] = y;
        while(z--) {
            int u, v = i, w; cin>>u>>w;
            make(u, v, w);
        }
    }
    for(int i = 1; i <= n; i++) {
        Dijkstra(0, l[i], l[i] + a);
        ans = min(ans, d[1]);
    }
    cout<<ans<<endl;
    return 0;
}