AtCoder Regular Contest 083 D: Restoring Road Network

题意

有一张无向带权连通图(点数<=300),给出任意两点i,j之间的最短路长度dis[i][j].问是否存在一张这样的无向图.如果不存在输出-1.如果存在输出所有这样的无向图中边权和最小的一张的边权和.

分析

如果存在i,j,k(i,j,k互不相同)使得dis[i][k]+dis[k][j]<dis[i][j]那么一定不存在.否则一定存在.

对于i,j(i!=j),如果存在第三个点k使得dis[i][k]+dis[k][j]=dis[i][j],那么为了总的边权和最小,i和j必然没有连边,i和j之间的最短路径是从i到k的最短路径和k到j的最短路径连接起来得到的.

如果不存在这样的k,i和j之间必然存在一条边权为dis[i][j]的边.

O(n^3)完事了.

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=305;

int dis[maxn][maxn];

bool notneed[maxn][maxn];

int main(){

  int n;scanf("%d",&n);

  for(int i=1;i<=n;++i){

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

      scanf("%d",&dis[i][j]);

    }

  }

  bool flag=true;

  for(int i=1;i<=n;++i){

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

      for(int k=1;k<=n;++k){

	if(i!=j&&j!=k&&k!=i){

	  if(dis[i][j]+dis[j][k]<dis[i][k])flag=false;

	  if(dis[i][j]+dis[j][k]==dis[i][k])notneed[i][k]=true;

	}

      }

    }

  }

  if(!flag){

    printf("-1\n");

  }else{

    long long ans=0;

    for(int i=1;i<=n;++i){

      for(int j=i+1;j<=n;++j){

	if(!notneed[i][j])ans+=dis[i][j];

      }

    }

    printf("%lld\n",ans);

  }

  return 0;

}

巴特西

AtCoder Regular Contest 083 D: Restoring Road Network

题意

分析

最新文章

热门文章