当前位置：首页 -> 基础 -> c++编程基础

POJ 3835 Columbus's bargain （最短路径 spfa 算法）(二)

2014-11-23 23:40:17 · 作者: · 浏览: 12
标签: POJ 3835 Columbus' bargain 路径 spfa 算法
一条权值V-1的单向边）
3、物品价值相等 时物物交换 （将两个物品之间添一条权值为0的双向边）
4、物物价值不等时交换需要花C金币　（将Ａ到Ｂ添一条权值为Ｃ的双向边）
按照构图，算一下单源最短路径 
#include   
#include   
#include   
#include   
using namespace std;  
  
const int maxn=30;  
  
struct edge{  
    int u,v,w,next;  
    edge(int u0=0,int v0=0,int w0=0,int next0=0){  
        u=u0;v=v0;w=w0;next=next0;  
    }  
}e[maxn*maxn];  
  
int n,head[maxn],cnt,price[maxn],from,dist[maxn];  
bool visited[maxn];  
  
void initial(){  
    from=0;cnt=0;  
    for(int i=0;i<=n;i++){  
        visited[i]=false;  
        head[i]=-1;dist[i]=200000000;  
    }  
}  
  
void adde(int u,int v,int w){  
    e[cnt].u=u,e[cnt].v=v,e[cnt].w=w,e[cnt].next=head[u],head[u]=cnt++;  
}  
  
void input(){  
    int m,x,y,z;  
    for(int i=0;i>x>>y;  
        price[x]=y;  
        adde(from,x,y-1);  
    }  
    for(int i=1;i<=n;i++){  
        for(int j=i+1;j<=n;j++){  
            if(price[i]==price[j]){  
                adde(i,j,0);  
                adde(j,i,0);  
            }  
        }  
    }  
    cin>>m;  
    while(m-- >0){  
        cin>>






x>>y>>z;  
        adde(x,y,z);  
    }  
}  
  
void spfa(){  
    queue  q;  
    int s=from,d;  
    dist[from]=0;  
    q.push(s);  
    visited[s]=true;  
    while(!q.empty()){  
        s=q.front();  
        q.pop();  
        for(int i=head[s];i!=-1;i=e[i].next){  
            d=e[i].v;  
            if(dist[d]>dist[s]+e[i].w){  
                dist[d]=dist[s]+e[i].w;  
                if(!visited[d]){  
                    visited[d]=true;  
                    q.push(d);  
                }  
            }  
        }  
        visited[s]=false;  
    }  
      
}  
  
void computing(){  
    int ans=0;  
    spfa();  
    for(int i=1;i<=n;i++){  
        cout<>t;  
    while(t-- >0){  
        cin>>n;  
        initial();  
        input();  
        computing();  
    }  
    return 0;  
}