Dijkstra-POJ-1062-高価な贈り物

8473 ワード

高価な贈り物Time Limit:1000 MS Memory Limit:10000 K Total Submissions:41711 Accepted:12188 Description
若い探検家がインディアン部族に来た.そこで彼は酋長の娘と愛し合って、酋長に縁談を求めた.酋長は彼に10000個の金貨を結納として頼んで、娘を彼と結婚することを承諾した.探検家はこんなにたくさんの金貨を出せないので、酋長に要求を下げるように頼んだ.酋長は言った.「ええ、もしあなたが私のために大祭司の毛皮の上着を手に入れることができたら、私は8000金貨しかありません.もしあなたが彼の水晶球を手に入れることができたら、5000金貨だけでいいです.」探検家は大祭司のところに行って、彼に毛皮の上着や水晶のボールを要求して、大祭司は彼に金貨で交換して、あるいは彼のために他のものを持ってきて、彼は価格を下げることができます.探検家はまた他の場所に駆けつけ、他の人も似たような要求をしたり、金貨で交換したり、他のものを見つけたりして価格を下げることができます.しかし、探検家は多様なもので同じものを交換する必要はありません.もっと低い価格は得られないからです.探検家は今あなたの助けが必要で、彼に最小限の金貨で自分の心の上の人と結婚させます.また、彼があなたに伝えたいのは、この部族では、等級観念が非常に厳しいことです.地位の格差が一定の制限を超えた2人の間では、取引を含むいかなる形式の直接接触も行わない.彼は外来者なので、これらの制限を受けなくてもいいです.しかし、もし彼がある地位の低い人と取引をしたら、地位の高い人はもう彼と取引しません.彼らはこれが間接的な接触に等しいと思っています.逆に同じです.そのため、すべての状況を考えてから彼に最高の案を提供する必要があります.便宜上、私たちはすべてのものを1から番号付けし、酋長の承諾も1つのものと見なし、番号はいつも1です.各品目には、対応する価格P、所有者の地位等級L、および一連の代替品Tiとその代替品に対応する「優遇」Viがある.2人の地位格差がMを超えると、「間接取引」はできない.これらのデータに基づいて、探検家が酋長の娘と結婚するには少なくともいくらの金貨が必要かを計算しなければなりません.Input
入力1行目は2つの整数Mで、N(1<=N<=100)は、地位格差制限と物品の総数を順次表す.次に、N個の物品の記述を小さいものから大きいものまで番号順に示す.各物品の記述の先頭には、3つの非負の整数P、L、Xがある(X最低必要な金貨数を出力します.Sample Input
1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0 Sample Output
5250 Source
浙江省
めったに見られない中国語の問題ですね.個人的には中国語の問題が好きではありません.簡単ではないので、とても難しいです.私のような大水品にとってはあまり有利ではありません.この問題は一人一人の物品を抽象的に点とすべきで、各個人の間の物交換あるいは直接購入方式は抽象的に一方向の経路で、必要な金貨は権値として、しかも直接購入は起点からその点までの経路の権値である.この問題の難点は,等級制限にあり,取引範囲を列挙することにより,取引範囲外の人visit[i]=1としてdijkstraアルゴリズムを行う.すべての人が間接的な接触の存在を許さないため、最低レベルlv[i]を1つ確定すれば、取引範囲は必ず[lv[i],lv[i]+M]であるため、列挙によって漏解しないこと、すなわちn回Dijkstraを行うことを確保する.ここでは優先キューを使用して最適化します.
//
// main.cpp
//      -M-     
//
// Created by     on 15/10/18.
// Copyright © 2015     . All rights reserved.
//
// 16ms 912KB

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
#define MAXN 10005
using namespace std;

long long int m,n;

struct qnode {
    int v;
    long long int c;
    qnode(int _v=0,long long int _c=0):v(_v),c(_c){}
    bool operator <(const qnode &r)const
    {
        return c>r.c;
    }
};
struct Edge
{
    int v;
    long long int cost;
    Edge(int _v=0,long long int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
bool vis[MAXN];
long long int dist[MAXN],level[105],lvmax;
void Dijkstra()
{
    for (int i=1; i<=n; i++) {
        dist[i]=INF;
    }
    priority_queue<qnode>que;
    while (!que.empty()) {
        que.pop();
    }
    dist[0]=0;
    que.push(qnode(0,0));
    qnode tmp;
    while (!que.empty()) {
        tmp=que.top();
        que.pop();
        int u=tmp.v;
        if (vis[u]) {
            continue;
        }
        vis[u]=1;
        for (int i=0; i<E[u].size(); i++) {
            int v=E[tmp.v][i].v;
            long long int cost=E[u][i].cost;
            if (!vis[v] && dist[v]>dist[u]+cost && level[v]<=lvmax) {
                dist[v]=dist[u]+cost;
                que.push(qnode(v,dist[v]));
            }
        }
    }
}
void addedge(int u,int v,long long int w)
{
    E[u].push_back(Edge(v,w));
}
int main(int argc, const char * argv[]) {
    long long int c,out=INF;
    int a,total;
    memset(level, 0, sizeof(level));
    cin >> m >> n;
    for (int i=1; i<=n; i++) {
        scanf("%lld %lld %d",&c,&level[i],&total);
        addedge(0, i, c);
        for (int j=1; j<=total; j++) {
            scanf("%d %lld",&a,&c);
            addedge(a, i, c);
        }
    }
    for (int i=1; i<=n; i++) {
        memset(vis, 0, sizeof(vis));
        lvmax=level[i]+m;
        for (int j=1; j<=n; j++) {
            if (level[j]<level[i] || level[j]>lvmax) {
                vis[j]=1;
            }
        }
        Dijkstra();
        out=min(out,dist[1]);
    }
    cout << out << endl;
    return 0;
}