随笔-68  评论-10  文章-0  trackbacks-0
枚举+最短路
枚举最低等级,保证酋长在交易范围,然后求最短路。
#include<iostream>
using namespace std;

const int inf=100000000;
int m,n;
int map[105][105];
int dis[105],vis[105],lev[105];

int dijkstra()
{
    
int ans=inf;
    
int i,j,k;
    
for(i=lev[1]-m;i<=lev[1];i++)
    
{
        memset(vis,
0,sizeof(vis));
        
for(j=1;j<=n+1;j++)
            dis[j]
=map[1][j];
        vis[
1]=1;

           
for(j=1;j<=n;j++)
        

            
int min=inf,cur=-1;
            
for(k=1;k<=n+1;k++)
            
{
                
if(!vis[k]&&lev[k]>=i&&lev[k]<=i+m&&dis[k]<min)
                
{
                    min
=dis[k];
                    cur
=k;
                }

            }

            
if(cur==-1break;
            vis[cur]
=1;

            
for(k=1;k<=n+1;k++)
            
{
                
if(!vis[k]&&lev[k]>=i&&lev[k]<=i+m&&map[cur][k]!=inf&&dis[k]>dis[cur]+map[cur][k])
                    dis[k]
=dis[cur]+map[cur][k];
            }

        }

        
if(dis[n+1]<ans)
            ans
=dis[n+1];
    }

    
return ans;
}


int main()
{
    
int p,l,x,t,v;
    
int i,j;
    scanf(
"%d%d",&m,&n);
    
for(i=1;i<=n;i++)
        
for(j=1;j<=n;j++)
        
{
            
if(i==j) map[i][j]=0;
            
else map[i][j]=inf;
        }
 
    
for(i=1;i<=n;i++)
    
{
        scanf(
"%d%d%d",&p,&l,&x);
        map[i][n
+1]=p;
        lev[i]
=l;
        
for(j=1;j<=x;j++)
        
{
            scanf(
"%d%d",&t,&v);
            map[i][t]
=v;
        }

    }

    lev[n
+1]=lev[1];
    printf(
"%d\n",dijkstra());
    
return 0;
}
posted on 2010-08-11 16:40 wuxu 阅读(196) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理