[POJ][3835][单源最短路] Columbus’s bargain

前言

首先恭喜自己，终于写出了能在POJ上排第一名的代码。其次为自己惋惜下，判重时少了个“j!=x”的条件，找了n久才发现这个小bug，这要是在赛场上，肯定悔死了。首先用spfa做，怎么都找不出错误，甚至以为自己模板写错了，再用dijkstra做，发现依然wa，才觉得不是模板问题。

题目大意

哥伦布要从野人手里买20种货物。用以下四种种方法可以买到货物：

按货物的价格（以金币为单位）付足金币。
对于每个货物，可以用一个玻璃珠代替一个金币。
用等价的其他种类货物交换。
用价格更低的货物加上金币来交换。

问每种物品至少需要花多少金币才能买到。

思路

最短路，将每个物品抽象成节点，源点是虚拟的，源点与其他节点之间的边的权值就是物品价格。

注意物品价格相等时可以交换的条件，也就是说，此时两个节点应用一条权值为0的边相连。

代码

首先是用spfa写出的代码：

#include
#include
using namespace std;
#define datasize 20+1
#define maximum 2147483647
int map[datasize+1][datasize+1],d[datasize+1],mark[datasize+1],n,m;
void initialize_single_source(int s)
{
    for(int i=1;i<=n;i++)
        d[i]=maximum;
    d[s]=0;
}
void relax(int u,int v)
{
    if(d[v]>d[u]+map[u][v])
        d[v]=d[u]+map[u][v];
}
void spfa(int s)
{
    initialize_single_source(s);
    queue q;
    for(int i=1;i<=n;i++)
        mark[i]=false;
    q.push(s);
    mark[s]=true;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        mark[u]=false;
        for(int i=1;i<=n;i++)
            if(i!=u&&map[u][i]!=maximum)
            {
                int temp=d[i];
                relax(u,i);
                if(d[i]0;t--)
    {
        scanf("%d",&n);
        n++;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                map[i][j]=maximum;
        for(int i=0;i

接着是dijkstra（堆优化）的做法：

#include
#include
using namespace std;
#define datasize 20+1
#define maximum 2147483647
int a[datasize+1],heap_size_a,v[datasize+1],map[datasize+1][datasize+1],length_a,n,m,result[datasize+1];
int parent(int i)
{
    return i/2;
}
int left(int i)
{
    return 2*i;
}
int right(int i)
{
    return 2*i+1;
}
void min_heapify(int a[],int i)
{
    int l=left(i),r=right(i),least;
    if(l<=heap_size_a&&a[l]=1;i--)
        min_heapify(a,i);
}
int heap_extract_min(int a[])
{
    int min=v[1];
    result[v[1]]=a[1];
    a[1]=a[heap_size_a];
    v[1]=v[heap_size_a];
    heap_size_a--;
    min_heapify(a,1);
    return min;
}
void heap_decrease_key(int a[],int i,int key)
{
    a[i]=key;
    while(i>1&&a[parent(i)]>a[i])
    {
        swap(a[i],a[parent(i)]);
        swap(v[i],v[parent(i)]);
        i=parent(i);
    }
}
void initialize_single_source(int s)
{
    length_a=n;
    for(int i=1;i<=length_a;i++)
    {
        a[i]=maximum;
        v[i]=i;
    }
    a[s]=0;
}
void relax(int i,int j)
{
    if(a[j]>result[i]+map[i][v[j]])
        heap_decrease_key(a,j,result[i]+map[i][v[j]]);
}
void dijkstra(int s)
{
    initialize_single_source(s);
    build_min_heap(a);
    while(heap_size_a>=1)
    {
        int u=heap_extract_min(a);
        for(int i=1;i<=heap_size_a;i++)
            if(map[u][v[i]]!=maximum)
                relax(u,i);
    }
}
bool check(int x)
{
    for(int i=2;i<=n;i++)
        for(int j=2;j<=n;j++)
            if(i!=x&&j!=i&&j!=x&&result[x]==result[i]+result[j])
                return true;
    return false;
}
int main()
{
    int t;
    for(scanf("%d",&t);t>0;t--)
    {
        scanf("%d",&n);
        n++;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                map[i][j]=maximum;
        for(int i=0;i

前言

题目大意

思路

代码

发表回复 取消回复

发表回复取消回复