【2019.10.29】

Problemset   Solution（chrome里只能复制链接后粘贴打开）

最新学习状态&考试状态都不对，心态也有点不好，自己要去调节一下。 

同时刷题速度还不够。这样是拿不到省一的。

趁着最后的时间，拼命努力吧。

T1.

FLoyd很好想，但我卡数据卡太死了觉得会TLE就没写，同时也是没注意出题人写的时间可放宽到1.3倍。

考虑用可以按特定顺序加点的Floyd。注意这种要维护两个最大/最小的问题一般都是一个靠排序一个靠max/min（∵不能两个同时考虑，只能先类似于处理出一个）。

注意排序只能保证点k值在路径中最大，两个端点点值可能比他大，所以要max这三个点的点值。

我改的时候还搞错了它的数值大小，一个要开ll，一个必须要开int，两者做乘法才不会超大小。以后记得比较精准的估算一下数据大小。

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define For(i,l,r) for(ri i=l;i<=r;i++)
#define Dfor(i,r,l) for(ri i=r;i>=l;i--)
using namespace std;
const int M=450;
ll ans;
ll n,m,p[M],e[M][M],dis[M][M],v[M];
inline ll read(){
    ll f=1,sum=0;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();}
    return f*sum;
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline bool cmp(int x,int y){return p[x]<p[y];}
int main(){
    freopen("goaway.in","r",stdin);
    freopen("goaway.out","w",stdout);
    n=read(),m=read();
    For(i,1,n) v[i]=i,p[i]=read();
    sort(v+1,v+n+1,cmp);
    For(i,1,n){
        For(j,1,n){
            e[i][j]=1e9,dis[i][j]=1e18;
        }
    }
    For(i,1,m){
        ll u=read(),v=read(),w=read();
        e[u][v]=w;
    }
    For(k,1,n){
        For(i,1,n){
            For(j,1,n){
                e[i][j]=min(max(e[i][v[k]],e[v[k]][j]),e[i][j]);
                dis[i][j]=min(dis[i][j],1ll*e[i][j]*max(max(p[i],p[j]),p[v[k]]));
            }
        }
    }
    For(i,1,n){
        For(j,1,n){
            ans+=(i!=j)*dis[i][j];
        }
    }
    printf("%lld
",ans);
    return 0;
}

T3.