poj 1062 비 싼 예물 (dijkstra 최 단 길)

제목 링크: http://poj.org/problem?id=1062
값 비 싼 예물
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 36799
 
Accepted: 10616
Description
젊 은 탐험가 가 인디언 부족 에 왔 다.그곳 에서 그 는 추장 의 딸 과 사랑 에 빠 져 추장 에 게 청혼 을 했다.추장 은 그 에 게 만 개의 금 화 를 예물 로 달라 고 해서 야 딸 을 그 에 게 시집 보 내 겠 다 고 대답 했다.탐험 가 는 이렇게 많은 금 화 를 꺼 내지 못 하고 추장 에 게 요 구 를 낮 춰 달라 고 부탁 했다.추장 은 "응, 대사 제의 가죽 저고리 만 구 해 주면 8000 금화 만 구 해 줄 수 있어. 수정 구 를 구 해 오 면 5000 금화 면 돼." 라 고 말 했다. 탐험 가 는 대사 제 에 게 달 려 가 가죽 저고리 나 수정 구 를 요구 했다. 대사 제 는 금화 로 바 꿔 달라 고 하거나 다른 물건 을 구 해 오 면 가격 을 낮 출 수 있 었 다.탐험 가 는 다른 곳 으로 달 려 가 비슷 한 요 구 를 하거나 금화 로 바 꾸 거나 다른 물건 을 찾 으 면 가격 을 낮 출 수 있다.하지만 탐험 가 는 더 낮은 가격 을 받 지 못 하기 때문에 다양한 물건 으로 바 꿀 필요 가 없다.탐험 가 는 이제 최소한 의 금화 로 마음 에 드 는 사람 을 얻 을 수 있 도록 당신 의 도움 이 필요 합 니 다.그리고 그 가 너 에 게 알려 주 고 싶 은 것 은 이 부락 에서 등급 관념 이 매우 삼엄 하 다 는 것 이다.지위 격차 가 일정한 제한 을 초과 한 두 사람 사이 에는 거래 를 포함 한 어떠한 형식의 직접적인 접촉 도 하지 않 는 다.그 는 외지인 이기 때문에 이런 제한 을 받 지 않 아 도 된다.그러나 그 가 어떤 지위 가 낮은 사람과 거래 를 했다 면 지위 가 높 은 사람 은 더 이상 그 와 거래 하지 않 을 것 이다. 그들 은 이것 이 간접 적 인 접촉 과 같 고 반대로 도 마찬가지 라 고 생각한다.그래서 모든 상황 을 고려 한 후에 그 에 게 가장 좋 은 방안 을 제공 해 야 한다.
  편 의 를 위해 우 리 는 모든 물품 을 1 부터 번 호 를 매기 고 추장 의 승낙 도 하나의 물품 으로 간주 하 며 번 호 는 항상 1 이다.모든 물품 은 해당 하 는 가격 P, 주인의 지위 등급 L, 그리고 일련의 대체 품 Ti 와 해당 대체 품 에 대응 하 는 '혜택' Vi 가 있다.두 사람의 지위 등급 격차 가 M 을 넘 으 면 '간접 거래' 가 불가능 하 다.탐험 가 는 최소한 얼마의 금화 가 필요 해 야 추장 의 딸 을 얻 을 수 있 는 지 이 데 이 터 를 근거 로 계산 해 야 한다. 
Input
첫 줄 을 입력 하면 두 개의 정수 M, N (1 & lt; = N & gt; = 100) 으로 지위 등급 차이 제한 과 아 이 템 의 총 수 를 순서대로 나타 낸다.이 어 번호 에 따라 어 릴 때 부터 차례대로 N 개의 아 이 템 에 대한 설명 을 했다.각 아 이 템 의 설명 은 처음에 세 개의 비 마이너스 정수 P, L, X (X < N) 로 이 아 이 템 의 가격, 주인의 지위 등급 과 대체 품 총 수 를 순서대로 나타 낸다.그 다음 에 X 줄 은 각 줄 에 두 개의 정수 T 와 V 를 포함 하여 각각 대체 품 의 번호 와 '우대 가격' 을 나타 낸다.
Output
수출 에 최소 필요 한 금화 수 입 니 다.
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
저장 성
제목 대의: (1) 입력 을 map [] [] 로 전환 합 니 다. 그 중에서 송금 점 t 를 추가 하면 모든 아 이 템 이 송금 점 t 와 연결 되 고 권한 수 치 는 혜택 이 없 는 상황 에서 의 금화 수 입 니 다.
(2) 탐험가 가 M 범위 내 에서 만 거래 할 수 있 고 M 범위 에 추장 의 등급 이 포함 되 어야 한 다 는 것 을 분석 했다.
(3) 문제 의 의 미 를 만족 시 키 는 범위 에 대해 dijkstra 알고리즘 이 가장 짧 은 경 로 를 찾 았 다.
(4) 모든 경로 에서 두 점 의 등급 차 이 는 반드시 제한 안에 있어 야 한다.
이것 은 아주 간단 한 템 플 릿 문 제 는 아니 지만, 각 세부 사항 에 주의 하면 된다.
 
코드 참조
 

 1 #include <iostream>

 2 #include <cstdio>

 3 using namespace std;

 4 int vis[105],map[105][105],node[105],Min,n,w;

 5 const int INF=99999999;

 6 

 7 int dijkstra()

 8 {

 9     for(int i=1; i<=n; i++)

10     {

11         node[i]=map[0][i];

12     }

13     for (int k=1; k<=n; k++)

14     {

15         Min=INF;

16         for (int i=1; i<=n; i++)

17             if (!vis[i])

18             {

19                 if (Min>node[i])

20                 {

21                     Min=node[i];

22                     w=i;

23                 }

24             }

25         vis[w]=1;

26         for (int i=1; i<=n; i++)

27             if (!vis[i])

28                 if (node[i]>map[w][i]+node[w])

29                     node[i]=map[w][i]+node[w];

30 

31     }

32     return node[1];

33 }

34 

35 int main ()

36 {

37     int m,l[105];

38     while (cin>>m>>n)

39     {

40         for (int i=1; i<=n; i++)

41         {

42             node[i]=INF;

43             for (int j=1; j<=n; j++)

44                 map[i][j]=INF;

45         }

46         int MM=INF;

47         for (int i=1; i<=n; i++)

48         {

49             int p,x;

50             cin>>p>>l[i]>>x;

51             while (x--)

52             {

53                 int t,v;

54                 cin>>t>>v;

55                 map[t][i]=v;

56             }

57             map[0][i]=p;

58         }

59         for (int i=1; i<=n; i++)

60         {

61             int lv=l[i];

62             //l[i]+m l[i]

63             for (int j=1; j<=n; j++)

64             {

65                 if (l[j]>=lv&&l[j]<=lv+m)

66                     vis[j]=0;

67                 else

68                     vis[j]=1;

69             }

70             int s=dijkstra();

71             MM=min(s,MM);

72         }

73         printf ("%d
",MM);

74     }

75     return 0;

76 }