一道普及-的……%%%大佬
by bztMinamoto @ 2018-08-10 20:38:50
@[cy1306110516](/space/show?uid=98390) %%%
by 小云力月永 @ 2018-08-10 20:56:30
%%%太强啦
by Bay_Max @ 2018-08-10 21:00:29
# 关于SPFA
- 他死了
by Viston @ 2018-08-10 21:06:46
@[HNFMS__viston](/space/show?uid=107101) QAQ
by ChthollyTree @ 2018-08-20 18:58:17
%%%%%%大佬orz
by 黄柠檬11 @ 2018-08-21 08:56:43
# 关于SPFA
- 他死了
by wxy_god @ 2018-08-21 13:24:58
~~@SPFA~~
by AmlyC @ 2018-08-27 19:12:37
```cpp
// 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:09:24
我写的只有44，哪位大佬帮我看看
by AmlyC @ 2018-08-27 21:10:29