只会SPFA的我，求大佬帮忙看看

AmlyC @ 2018-08-27 21:12:53

#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:13:34

有几个dis[i]总是为0....

by 小粉兔 @ 2018-08-27 21:15:50

    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;
    }

连边有问题

by 小粉兔 @ 2018-08-27 21:19:43

（你这说是SPFA，不就是DP吗，更新顺序完全相同

by AmlyC @ 2018-08-27 21:21:49

@小粉兔

    fors(i,1,n-1){
        fors(j,1,i){
            add(k+j-1,k+j-1+i,a[i+1][j]);printf("%d %d %d\n",k+j-1,k+j-1+i,a[i+1][j]);
            add(k+j-1,k+j+i,a[i+1][j+1]);printf("%d %d %d\n",k+j-1,k+j+i,a[i+1][j+1]);
        }
        k+=i;
    }

by AmlyC @ 2018-08-27 21:22:42

@小粉兔 我只是无聊，想写个SPFA

by 小粉兔 @ 2018-08-27 21:27:29

如何？还是过不去吗

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

@小粉兔

```cpp
#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,-1,sizeof dis);
    vis[1]=1,dis[1]=a[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];
        }
    }
    add(1,1,ans[1]);
    k=t=1;
    fors(i,1,n-1){
        fors(j,1,i){
            add(k+j-1,k+j-1+i,a[i+1][j]);printf("%d %d %d\n",k+j-1,k+j-1+i,a[i+1][j]);
            add(k+j-1,k+j+i,a[i+1][j+1]);printf("%d %d %d\n",k+j-1,k+j+i,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:30:23

@小粉兔 超时。。。

by AmlyC @ 2018-08-27 21:31:20

@小粉兔 等一下

by AmlyC @ 2018-08-27 21:32:33

@小粉兔

#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,-1,sizeof dis);
    vis[1]=1,dis[1]=a[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+j-1+i,a[i+1][j]);
            add(k+j-1,k+j+i,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;
}

AC了