O2人 @ 2018-08-10 20:35:15

#include <bits/stdc++.h>
#define F freopen
#define F_ {F("1.in","r",stdin);F("1.out","w",stdout);}
#define maxn 500505
#define maxe 1001005
using namespace std;
inline int read(){
    int x=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}
int lnk[maxn],w[maxe],son[maxn],nxt[maxn],tot,dis[maxn],q[maxn],n,a[1005][1005],ans,flg;
bool vis[maxn];
void add_e(int x,int y,int z){w[++tot]=z;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
void SPFA(){
    memset(dis,192,sizeof dis);
    int hed=0,til=1;
    vis[1]=1,q[1]=1,dis[1]=a[1][1];
    while (hed!=til){
        vis[++hed%=maxn]=0;
        for (int j=lnk[q[hed]];j;j=nxt[j]){
            if (dis[son[j]]>dis[q[hed]]+w[j]) continue; 
            dis[son[j]]=dis[q[hed]]+w[j];
            if (!vis[son[j]]) vis[son[j]]=1;q[++til%=maxn]=son[j];
            int now=hed+1;
            if (dis[q[now]]<dis[q[til]]) swap(q[now],q[til]);
        }
    }
}
int main(){
    F_;
    n=read();
    for (int i=1;i<=n;i++)
    for (int j=1;j<=i;j++) {
        a[i][j]=read();
    }
    for (int i=1;i<n;i++)
    for (int j=1;j<=i;j++) {
        if (j==i&&i<n) flg+=i;
        int begin=flg+1,end=flg+i;
        for (int k=begin;k<=end;k++) add_e(i,k,a[i][j]);
    }
    SPFA();
    ++flg;
    for (int i=flg;i<=flg+n;i++) ans=max(ans,dis[i]);
    printf("%d\n",ans);
    return 0;
}

by bztMinamoto @ 2018-08-10 20:38:50

一道普及-的……%%%大佬

by 小云力月永 @ 2018-08-10 20:56:30

@cy1306110516 %%%

by Bay_Max @ 2018-08-10 21:00:29

%%%太强啦

by Viston @ 2018-08-10 21:06:46

关于SPFA

• 他死了

by ChthollyTree @ 2018-08-20 18:58:17

@HNFMS__viston QAQ

by 黄柠檬11 @ 2018-08-21 08:56:43

%%%%%%大佬orz

by wxy_god @ 2018-08-21 13:24:58

关于SPFA

• 他死了

by AmlyC @ 2018-08-27 19:12:37

@SPFA

by AmlyC @ 2018-08-27 21:09:24

// luogu-judger-enable-o2
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
const int SIZE=1<<20;
inline char getch(){
    static char buf[SIZE],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2) ? EOF : *p1++;
}
int read(){
    int s=0,f=1;
    char c=getch();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=getch();}
    while(c>='0'&&c<='9') {s=(s<<1)+(s<<3)+c-'0';c=getch();}
    return s*=f;
}
const int maxn=1000007;
int n,t,k,a[1001][1001],head[maxn],tot,vis[maxn],dis[maxn],ans[maxn];
struct node
{
    int to,next,val;
}edge[maxn];

void add(int x,int y,int w){
    edge[++tot].to=y,edge[tot].next=head[x],head[x]=tot,edge[tot].val=w;
}

void spfa(){
    queue<int> q;
    memset(dis,0,sizeof dis);
    dis[1]=a[1][1],vis[1]=1;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=edge[i].next){
            if(dis[edge[i].to] <= dis[u]+edge[i].val){
                dis[edge[i].to] = dis[u]+edge[i].val;
                if(!vis[edge[i].to]){
                    q.push(edge[i].to);
                    vis[edge[i].to]=1;
                }
            }
        }
    }
}
int main(int argc, char const *argv[])
{
    memset(a,-1,sizeof a);
    n=read();
    fors(i,1,n){
        fors(j,1,i){
            a[i][j]=read();
            ans[++t]=a[i][j];
        }
    }
    k=t=1;
    fors(i,1,n-1){
        fors(j,1,i){
            add(k+j-1,k+i,a[i+1][j]);
            add(k+j-1,k+i+1,a[i+1][j+1]);
        }
        k+=i;
    }
    spfa();
    k=(n*(n+1))>>1;
    t=k-n;
    int maxs=-1;
    fors(i,t,k){
        maxs=max(dis[i],maxs);
    }
    printf("%d\n",maxs);
    return 0;
}

by AmlyC @ 2018-08-27 21:10:29

我写的只有44，哪位大佬帮我看看