T145192 【2020.8.23NOIP模拟赛】最优路线【DP&Floyd】

这道题主要思想就是修改 $Floyd$ 为一个奇怪的 $DP$ ?
然后各种玄学优化+卡常，这样就能 $O(n^3)$ 切掉这道题。

我们定义 $ans$_i,j 作为转移变量，表示 $i$ 号点到 $j$ 号点的
$\min(最大路径长度 \times 路径上的最大点权)$
可得动态转移方程：
$ans[i][j]=\min(ans[i][j],\max(dq2[i],\max(dq2[j],dq2[k]))*a[i][j])$
这里解释一下各种数组的含义：

• $po$ 表示点权和边权
• $a$ 是两点之间的最大边权
• $dq2$ 是记录点权

代码解释

#pragma GCC optimize(2)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

long long a[501][501],ans[501][501],dq2[1000010];
long long n,m,x,y,w;

struct node
{
	long long dq,bh;
}po[1000010];
inline bool cmp(const node&a, const node&b)
{
	return a.dq<b.dq;
}
inline int read()
{
	register int X=0;
	register bool flag=1;
	register char ch=getchar();
	while(ch<'0'||ch>'9')
	 {
	   if(ch=='-')
	     flag=0; 
		 ch=getchar();
	 }
	while(ch>='0'&&ch<='9')
	 {
	    X=(X<<1)+(X<<3)+ch-'0';
		ch=getchar();
	 }
	if(flag) 
	  return X;
	return ~(X-1);
}
int main()
{
	memset(ans,0x7f,sizeof(ans));
	memset(a,0x7f,sizeof(a));
    n=read(),m=read();
    for(register int i=1; i<=n; i++)
     {
     	po[i].dq=read();
        dq2[i]=po[i].dq,po[i].bh=i,ans[i][i]=0;
     }
    sort(po+1,po+1+n,cmp);
    for(register int i=1; i<=m; i++)
     {
     	x=read(),y=read(),w=read();
     	a[x][y]=w,a[y][x]=w;
     	ans[x][y]=ans[y][x]=min(ans[x][y],a[x][y]*max(dq2[x],dq2[y]));  //初始化ans，输入一次做一次
     }
    for(register int h=1; h<=n; h++)
     {
     	long long k=po[h].bh;  //记录中转点
	    for(register int i=1; i<=n; i++)
	     for(register int j=1; j<=n; j++)
	      if(a[i][j]>max(a[i][k],a[k][j]))
	       {
	    	  a[i][j]=max(a[i][k],a[k][j]);  //先找最大边权
	    	  ans[i][j]=min(ans[i][j],max(dq2[i],max(dq2[j],dq2[k]))*a[i][j]); //DP
	       }
     }
    for(register int i=1; i<=n; i++)
     {
       for(register int j=1; j<=n; j++)
        {
      	  if(i==j)
      	    printf("0 ");
      	  else if(ans[i][j]==0)
      	    printf("-1 ");
      	  else
      	    printf("%lld ",ans[i][j]);
        }
	   printf("\n");
     }
    return 0;
}

本文地址：https://blog.csdn.net/Jackma_mayichao/article/details/108187565