poj1797 dijkstra

本文主要是介绍poj1797 dijkstra，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

 

  如题：http://poj.org/problem?id=1797

 

     题目给出一个没有负权的图，权代表承重亮，要求从起点到终点装的货物的最大值。

 

    将dijsktra的松弛操作略微更改dis[j]=MAX(dis[j],MIN(dis[k],a[k][j]));dij[j]是起点到j点可以载货的最大值，在dis[k]和a[k][j]中取一个最小值，然后再在它和dis[j]中取最大。

   

#include<iostream>
using namespace std;
#define MAXN 1005
int a[MAXN][MAXN];
int dis[MAXN];
bool vis[MAXN];
int MAX(int a,int b)
{return a>b?a:b;}
int MIN(int a,int b)
{return a>b?b:a;}

void dij(int v,int n)
{
 memset(vis,false,sizeof(vis));
 int i,j;
 for(i=1;i<=n;i++)
  dis[i]=a[v][i];
 vis[v]=true;
 for(i=1;i<n;i++)
 {
  int temp=-1,k=v;
  for(j=1;j<=n;j++)
  {
   if(vis[j]) continue;
   if(temp<dis[j])
   {
    temp=dis[j];
    k=j;
   }
  }
  vis[k]=true;
  for(j=1;j<=n;j++)
  {
   if(vis[j]) continue;
   dis[j]=MAX(dis[j],MIN(dis[k],a[k][j]));
  }
 }
}
int main()
{
 int N;
 cin>>N;
 int count=0;
 while(N--)
 {
  count++;
  memset(a,-1,sizeof(a));
  int n,m;
  scanf("%d %d",&n,&m);
  int i;
  for(i=1;i<=m;i++)
  {
   int t1,t2,w;
   scanf("%d %d %d",&t1,&t2,&w);
   a[t1][t2]=w;
   a[t2][t1]=w;
  }
  dij(1,n);
  printf("Scenario #%d:\n%d\n",count,dis[n]);
  printf("\n");
 }
}

 

这篇关于poj1797 dijkstra的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---