2014年12月15日 星期一

2014/12/15 POJ 1062 昂贵的聘礼

/*
    學習重點:
    最短路
*/
// http://poj.org/problem?id=1062
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define INF 2e9

typedef pair<int, int> di;
#define d first
#define i second

typedef vector<int>::iterator vit;

priority_queue<di, vector<di>, greater<di> > pri;

vector<di> v[200];
vector<int> vec;
int dis[200];

int M, N;
int P[200], L[200];

int lb;

void dijkstra()
{
    while( !pri.empty() )
    {
        int t = pri.top().i;
        int c = pri.top().d;
        pri.pop();

        if( dis[t] <= c ) continue;
        dis[t] = c;

        for(int vi = 0; vi < v[t].size(); vi++)
        {
            int nx = v[t][vi].i;
            int nc = v[t][vi].d;

            if( lb <= L[nx] && L[nx] <= lb+M )
                pri.push(di(c+nc, nx) );
        }
    }
}

int Ans = INF;

int main()
{
    scanf("%d %d", &M, &N);

    for(int Ni = 1; Ni <= N; Ni++)
    {
        scanf("%d %d", &P[Ni], &L[Ni]);
        vec.push_back(L[Ni]);

        int X;
        scanf("%d", &X);

        for(int Xi = 0; Xi < X; Xi++)
        {
            int t, c;
            scanf("%d %d", &t, &c);

            v[t].push_back(di(c, Ni) );
        }
    }

    sort(vec.begin(), vec.end());
    vit it = unique(vec.begin(), vec.end());
    vec.resize(it-vec.begin() );

    for(int vi = 0; vi < vec.size(); vi++)
    {
        lb = vec[vi];

        fill(dis, dis+200, INF);
        while( !pri.empty() ) pri.pop();

        for(int Ni = 1; Ni <= N; Ni++)
            if( lb <= L[Ni] && L[Ni] <= lb+M )
                pri.push(di(P[Ni], Ni) );

        dijkstra();

        Ans = min(Ans, dis[1]);
    }

    printf("%d\n", Ans);
}

沒有留言:

張貼留言