nyoj 昂贵的聘礼(Dijkstra)

思路：建图！！！之后枚举最大等级，求到物品1的最短路。

 1  
 2 #include <stdio.h>
 3 #include <queue>
 4 #include <string.h>
 5 #define maxn 0x3ffffff
 6 using namespace std;
 7 typedef pair<int,int> pii; 
 8 int visit[110],dis[110],map[110][110],n,m,v,l,p,x,t,vis[110],liv[110],sb,w,cas;
 9 priority_queue<pii,vector<pii>,greater<pii> >qq;
10 int main()
11 {    
12     int i,j,max;
13     while(scanf("%d%d",&m,&n)){
14         if(n==0&&m==0)
15             break;
16     memset(liv,0,sizeof(liv));
17     memset(map,9,sizeof(map));
18     sb=1;
19     max=0;
20     int sbsbsb=n;
21     while(sbsbsb--)
22     {        
23         scanf("%d%d%d",&p,&l,&x);
24         map[0][sb]=p;
25         liv[sb]=l;
26         if(liv[sb]>max)
27             max=liv[sb];
28         for(i=1;i<=x;i++)
29         {
30             scanf("%d%d",&t,&v);
31             map[t][sb]=v;
32         }
33         sb++;
34     }
35     int min=maxn;
36     for(i=0;i<=max;i++)
37     {
38         memset(visit,0,sizeof(visit));
39         memset(dis,9,sizeof(dis));
40         dis[0]=0;
41         qq.push(make_pair(dis[0],0));
42         while(!qq.empty())
43         {
44             pii u=qq.top();
45             qq.pop();
46             int x=u.second;
47             if(visit[x])
48                 continue;
49             visit[x]=1;
50             for(j=0;j<=n;j++)
51             {
52                 if(liv[j]>=(i-m)&&liv[j]<=i)
53                 {
54                     if(dis[j]>(dis[x]+map[x][j]))
55                     {
56                         dis[j]=dis[x]+map[x][j];
57                         qq.push(make_pair(dis[j],j));
58                     }
59                 }
60             }
61         }
62         if(dis[1]<min)
63             min=dis[1];
64     }
65     printf("%d
",min);
66     }
67     return 0;
68 }

标程

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#include<climits>
#include<string.h>
#include<cmath>
#include<stdlib.h>
#include<vector>
#include<set>
#define INF 1e7
#define MAXN 100010
#define maxn 111
#define maxm 1000
#define Mod 1000007
#define MIN(a,b) (a < b ? a : b)
#define MAX(a,b) (a > b ? a : b)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long LL;

int n, m, p, l, x;
int G[111][111], price[111], level[111];
int vis[111], dis[111];
int ans, k, t, v;

void init()
{
    memset(price,0,sizeof(price));
    memset(level,0,sizeof(level));
    for (int i = 0; i <= m; ++i)
        for (int j = 0; j <= m; ++j) {
            G[i][j] = INF;
        }
}

int Dijkstra()
{
    int pos, min;
    for (int i = 1; i <= m; ++i) dis[i] = price[i];
    for (int i = 1; i <= m; ++i) {
        min = INF;
        for (int j = 1; j <= m; ++j) {
            if (!vis[j] && min > dis[j]) {
                pos = j;
                min = dis[j];
            }
        }
        vis[pos] = 1;
        for (int j = 1; j <= m; ++j)
            if (!vis[j] && dis[pos] + G[pos][j] < dis[j])
                dis[j] = dis[pos] + G[pos][j];
    }

    return ans = MIN(ans,dis[1]);
}

void deal()
{
    ans = INF;
    for (int i = 1; i <= m; ++i) {
        int tmp = level[i];
        for (int j = 1; j <= m; ++j) {
            if (level[j] - tmp > n || tmp > level[j]) vis[j] = 1;
            else vis[j] = 0;
        }
        Dijkstra();
    }
    printf("%d
",ans);
}

void read()
{
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &price[i], &level[i], &k);
        for (int j = 0; j < k; ++j) {
            scanf("%d%d", &t, &v);
            G[t][i] = v;
        }
    }
}
void run()
{
    init();
    read();
    deal();
}

int main()
{
    while (~scanf("%d%d", &n, &m),n+m)
        run();
    return 0;
}