HDU 3268 Columbus’s bargain（最短路 Spfa）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3268

1
4
1 4
2 9
3 5
4 13
2
1 2 3
3 4 6

1 3
2 6
3 4
4 10
1

题意：

哥伦布和别人交易，用金币，交易规则：
1、每次买一个东西可以用一个玻璃珠代替1金币。
2、可以用相同的价格物品进行交换
3、如果对方愿意可以用N1+r金币交换到N2物品。
求最后每件物品的最小价格，并且最后输出有多少个物品价格=其他两个物品价格和。

PS:

首先建立一个源点S，然后连接所有的点，边上的权值为最初的价钱p - 1，然后在可用来交易的物品间建边，权值为R，然后价钱相等的物品再建边，权值为 0 ,求以S为源点的单源多点最短路；

代码如下：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctype.h>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define pi acos(-1.0)
#define INF 0xffffff
#define N 1005
#define M 2005
int n,m,k,Edgehead[N],dis[N];
struct
{
    int v,w,next;
} Edge[2*M];
bool vis[N];
int vv[N];
int cont[N];
void Addedge(int u,int v,int w)
{
    Edge[k].next = Edgehead[u];
    Edge[k].w = w;
    Edge[k].v = v;
    Edgehead[u] = k++;
}
void SPFA( int start)
{
    queue<int>Q;
    for(int i = 1 ; i <= n ; i++ )
        dis[i] = INF;
    dis[start] = 0;
    ++cont[start];
    memset(vis,false,sizeof(vis));
    Q.push(start);
    while(!Q.empty())//直到队列为空
    {
        int u = Q.front();
        Q.pop();
        vis[u] = false;
        for(int i = Edgehead[u] ; i!=-1 ; i = Edge[i].next)//注意
        {
            int v = Edge[i].v;
            int w = Edge[i].w;
            if(dis[v] > dis[u] + w)
            {
                dis[v] = dis[u]+w;
                if( !vis[v] )//防止出现环，也就是进队列重复了
                {
                    Q.push(v);
                    vis[v] = true;
                }
                //	if(++cont[v] > n)//有负环
                //		return -1;
            }
        }
    }
    //return dis[n];
}
int main()
{
    int t;
    int u,v,w;
    int n1, n2, r;
    int a, p;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        //scanf("%d%d",&m,&n);//n为目的地
        k = 1;
        memset(Edgehead,-1,sizeof(Edgehead));
        memset(vv,0,sizeof(vv));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d%d",&a,&p);
            vv[a] = p;
            Addedge(0,a,p-1);
        }
        scanf("%d",&m);
        for(int i = 1 ; i <= m ; i++ )
        {
            scanf("%d%d%d",&u,&v,&w);
            Addedge(u,v,w);
            //Addedge(v,u,w);//双向链表
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i!=j && vv[i]==vv[j])//价钱相等
                {
                    Addedge(i,j,0);//价钱相等权值就是零
                    Addedge(j,i,0);
                }
            }
        }
        SPFA(0);//从点0开始寻找最短路
        for(int i = 1; i <= n; i++)
        {
            printf("%d %d\n",i,dis[i]);
        }
        memset(vis,0,sizeof(vis));
        int num = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
//                if(i != j)
//                {
                for(int k = j+1; k <= n; k++)
                {
                    if(i != j)
                    {
                        if(!vis[i] && i!=k && dis[i]==dis[j]+dis[k])
                        {
                            vis[i] = true;
                            num++;
                        }
                    }
                }
            }
//            }
        }
        printf("%d\n",num);
    }
    return 0;
}

HDU 3268 Columbus’s bargain（最短路 Spfa）

原文：http://blog.csdn.net/u012860063/article/details/41050405