POJ1062

题目链接：http://poj.org/problem?id=1062

解题思路：

　　枚举区间+Dijkstra

　　一开始理解错了题意，WA了好久。后来参考题解才AC了。

　　把每一样物品看成一个点，由物品A换到物品B看成从A指向B的边，这样一来就把问题转换成最短路问题了，具体实现看代码吧。。。关键是枚举区间这一个细节。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int inf=0xfffffff;
const int maxn=100+10;
int thing[maxn],ranks[maxn],vis[maxn],d[maxn];
vector<pair<int,int> > vc[maxn];  //a,b           ,ma[maxn],mi[maxn]
int road[maxn][maxn];
int M,N,t;
int dijkstra(int l,int r){
    for(int i=1;i<=N;i++) {
        vis[i]=0;
        d[i]=inf;
    }
    d[1]=thing[1];
    while(1){
        int v=-1;
        for(int u=1;u<=N;u++){
            if(!vis[u]&&(v==-1||d[u]<d[v])) v=u;
        }
        if(v==-1)   break;
        vis[v]=1;
        for(int u=1;u<=N;u++){
            if(ranks[u]<=r&&ranks[u]>=l&&d[u]>d[v]+road[v][u]-thing[v]){
                d[u]=d[v]+road[v][u]-thing[v];
            }
        }
    }
    int ans=inf;
    for(int i=1;i<=N;i++){
        if(ans>d[i])    ans=d[i];
    }
    return ans;
}
int main(){
    scanf("%d%d",&M,&N);
    for(int i=1;i<=N;i++){
        scanf("%d%d%d",&thing[i],&ranks[i],&t);
        while(t--){
            int a,b;
            scanf("%d%d",&a,&b);
            vc[i].push_back(make_pair(a,b));
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=i;j<=N;j++){
            if(i==j)
                road[i][j]=thing[i];
            else
                road[i][j]=road[j][i]=inf;
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<vc[i].size();j++){
            int a=vc[i][j].first,b=vc[i][j].second;
            if(abs(ranks[a]-ranks[i])>M)    continue;
            road[i][a]=b+thing[a];
        }
    }
    int ans=inf;
    for(int i=ranks[1]-M;i<=ranks[1];i++){
        int temp=dijkstra(i,i+M);
        if(temp<ans)    ans=temp;
    }


    printf("%d
",ans);
    return 0;
}