poj1062

這個題目我最開始看題目看了半天，看不懂。。但是通過看樣例及答案終於看懂了。。。

首先先解決等級的關系。。如果等級越界，則不能交換。。所以原本等級的界限是

[rank[1]-m,rank[1]+m],但是這個邊界裡面會出現等級只差大於m，所以等級的區間應該是

[rank[1]-m,rank[1]],[rank[1]-m+1,rank[1]+1]............等等，所以一直枚舉到 [rank[1],rank[1]+m]..所以先通過枚舉得到可以交換的點。。然後就是題目的意思了。。。

我理解的優惠相當於是分解。。。比如如果得到1號物品需要得到2號物品和8000金幣。不就相當於1號到2號號為單向路勁，權值為8000.。。求各個點到1號點的最短路加上這個點的價值。。如圖所示。。。

1(10000)---------->2(1000)--------->4(50)

| 8000 200 |

|--------------------->3(3000)----------|

5000 200

畫圖之後一目了然。。。然後運用dijkstra解決。。。。。。。

希望各位指正我的想法。。

代碼如下：

#include
#include
#define INF 0x3f3f3f3f
const int maxn=100+10;
int m,n;
int vis[maxn],dis[maxn],e[maxn][maxn];
int withtin[maxn],value[maxn],ranki[maxn];

int dijkstra()
{
    int tmp,now,i,j;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    for(i=1;i<=n;i++)
    {
        tmp=INF;
        for(j=1;j<=n;j++)
        {
            if(!vis[j]&&withtin[j]&&dis[j]dis[now]+e[now][j])
                dis[j]=dis[now]+e[now][j];
        }
    }
    tmp=INF;
    for(i=1;i<=n;i++)
    {
        if(dis[i]+value[i]=ranki[1]-m+i&&ranki[j]<=ranki[1]+i)
                    withtin[j]=1;
            }
            cost=dijkstra();
             if(cost