昂贵的聘礼

POJ-1062-昂贵的聘礼

分析

建虚拟源点。

实现

#include <iostream>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 110;
int n, m;
int g[N][N], level[N];
int dis[N];
bool mark[N];

int dijkstra (int l, int r) { // 共 n + 1 个顶点
    memset(mark, 0, sizeof(mark));
    memset(dis, 0x3f, sizeof(dis));
    dis[0] = 0;

    for (int k = 1; k <= n; ++ k) {
        int cur = -1;
        for (int i = 0; i <= n; ++ i)
            if (mark[i] == false && (cur == -1 || dis[i] < dis[cur]))
                cur = i;
        mark[cur] = true;
        
        for (int i = 1; i <= n; ++ i)
            if (l <= level[i] && level[i] <= r)
                dis[i] = min(dis[i], dis[cur] + g[cur][i]);
    }
    return dis[1]; 
}

int main () {
    cin >> m >> n;
    memset(g, 0x3f, sizeof(g));
    for (int i = 0; i <= n; ++ i) g[i][i] = 0;
    for (int i = 1, p, x; i <= n; ++ i) {
        cin >> p >> level[i] >> x;
        g[0][i] = min(g[0][i], p);
        while (x --) {
            int t, v;
            cin >> t >> v;
            g[t][i] = min(g[t][i], v);
        }
    }

    int res = inf;
    for (int i = level[1] - m; i <= level[1]; ++ i)
        res = min(res, dijkstra(i, i + m));
    cout << res << endl;
    return 0;
}