前言
首先恭喜自己，终于写出了能在POJ上排第一名的代码。其次为自己惋惜下，判重时少了个“j!=x”的条件，找了n久才发现这个小bug，这要是在赛场上，肯定悔死了。首先用spfa做，怎么都找不出错误，甚至以为自己模板写错了，再用dijkstra做，发现依然wa，才觉得不是模板问题。
题目大意
哥伦布要从野人手里买20种货物。用以下四种种方法可以买到货物：
- 按货物的价格（以金币为单位）付足金币。
- 对于每个货物，可以用一个玻璃珠代替一个金币。
- 用等价的其他种类货物交换。
- 用价格更低的货物加上金币来交换。
问每种物品至少需要花多少金币才能买到。
思路
最短路，将每个物品抽象成节点，源点是虚拟的，源点与其他节点之间的边的权值就是物品价格。
注意物品价格相等时可以交换的条件，也就是说，此时两个节点应用一条权值为0的边相连。
代码
首先是用spfa写出的代码：
#include<iostream>
#include<queue>
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<int> 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]<temp&&!mark[i])
{
q.push(i);
mark[i]=true;
}
}
}
}
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&&d[x]==d[i]+d[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<n-1;i++)
{
int temp_1,temp_2;
scanf("%d%d",&temp_1,&temp_2);
map[1][temp_1+1]=temp_2-1;
}
scanf("%d",&m);
for(int i=0;i<m;i++)
{
int temp_1,temp_2,temp_3;
scanf("%d%d%d",&temp_1,&temp_2,&temp_3);
map[temp_1+1][temp_2+1]=temp_3;
}
for(int i=2;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(map[1][i]==map[1][j])
map[i][j]=map[j][i]=0;
spfa(1);
for(int i=0;i<n-1;i++)
printf("%d %d\n",i+1,d[i+2]);
int sum=0;
for(int i=2;i<=n;i++)
if(check(i))
sum++;
printf("%d\n",sum);
}
}
接着是dijkstra（堆优化）的做法：
#include<iostream>
#include<stdio.h>
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]<a[i])
least=l;
else
least=i;
if(r<=heap_size_a&&a[r]<a[least])
least=r;
if(least!=i)
{
swap(a[i],a[least]);
swap(v[i],v[least]);
min_heapify(a,least);
}
}
void build_min_heap(int a[])
{
heap_size_a=length_a;
for(int i=length_a/2;i>=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<n-1;i++)
{
int temp_1,temp_2;
scanf("%d%d",&temp_1,&temp_2);
map[1][temp_1+1]=temp_2-1;
}
scanf("%d",&m);
for(int i=0;i<m;i++)
{
int temp_1,temp_2,temp_3;
scanf("%d%d%d",&temp_1,&temp_2,&temp_3);
map[temp_1+1][temp_2+1]=temp_3;
}
for(int i=2;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(map[1][i]==map[1][j])
map[i][j]=map[j][i]=0;
dijkstra(1);
for(int i=0;i<n-1;i++)
printf("%d %d\n",i+1,result[i+2]);
int sum=0;
for(int i=2;i<=n;i++)
if(check(i))
sum++;
printf("%d\n",sum);
}
}