算法

(BFS) $O(n^3)$

其实虚拟源点其实是不必要的，建图方式有很多。
如果我们把两点之间的权值记作：优惠了的价格，即原价：10000，优惠价格8000，那么边权就是2000。
此时，从源点到这个点的距离就是之间经过的所有点(包括两个端点)的价值减去经过的路径的开销，因此这个时候只要从头开始跑bfs即可，注意等级限制。
//最后等级限制借鉴 https://www.acwing.com/solution/content/8233/
最后就是等级制度。我们可以枚举每个等级区间，每次求最短路是只能更新在这个区间里面的物品。枚举所有情况求一个最小值就可以了。 特别注意的是区间必须包含1点。 那么范围就是【L[1] - m, L[1]】

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std ;

const int N = 110 , M = N*N , INF = 0x3f3f3f3f;

int g[N][N] ;
int n , m ; //物品总数，等级限制
int ans , dist[N] ;
int q[M] ;

struct Node {
    int w , p ; //价格，等级
}node[N];

int bfs(int l , int r) //等级区间
{
    memset(dist , 0x3f , sizeof dist );
    dist[1] = node[1].w ;
    int ans = INF ;

    int hh = 0 , tt = 0 ;
    q[hh] = 1 ; 

    while(hh <= tt)
    {
        int u = q[hh++] ;
        Node t = node[u] ;

        ans = min(ans , dist[u]) ;

        //u和i之间有一条边并且点能遍历到
        for(int i = 1 ; i <= n ; i++)
        {
            if( g[u][i] && (l <= node[i].p && node[i].p <= r) ){  
                if(dist[u] - g[u][i] + node[i].w < dist[i])
                {
                    q[++tt] = i ;
                    dist[i] = dist[u] - g[u][i] + node[i].w ;
                }
            }
        }
    }

    return ans ;
}

int main()
{
    cin >> m >> n ; 
    for(int i = 1 ; i <= n ; i ++ )
    {
        int w , p , t ; //物品价值，等级，替代物品数量
        cin >> w >> p >> t ;
        node[i] = {w , p} ;
        for(int j = 0 ; j < t ; j++ )
        {
            int k , q ;
            cin >> k >> q ; //替换的物品编号，替换的价格
            g[i][k] = w - q ;
        }
    }

    int ans = INF ;
    for(int l = node[1].p-m ; l <= node[1].p ; ++l)
    {
        ans = min(ans , bfs(l , l+m) ) ;
    }

    cout << ans << endl;

    return 0;

}