Lvat_s Blog

据说网络流写得好也能过……orz常数帝们

我自己是看了周冬的论文——他来自芜湖一中。膜拜前辈！orzzzz

S-T图直接最短路就行了，注意建图即可。

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

int n,m,en,h[2000005],D[2000005],f[2000005],S,T;

struct Edge{
int b,v,next;
}e[7000005];

struct Node{
int u,v;
bool operator< (const Node &x) const{
return v>x.v?1:0;
}
};

priority_queue<Node> Q;

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void Dijkstra(){
memset(D,120,sizeof(D));
memset(f,0,sizeof(f));
while(!Q.empty())Q.pop();
Node tmp;
tmp.u=S;
D[S]=0;
tmp.v=0;
Q.push(tmp);
while(!Q.empty()){
    int u=Q.top().u;
    Q.pop();
    if(f[u])continue;
    if(u==T){printf("%d\n",D[T]);break;}
    f[u]=1;
    for(int i=h[u];i!=-1;i=e[i].next){
        int v=e[i].b;
        if(!f[v] && D[u]+e[i].v<D[v]){
            D[v]=D[u]+e[i].v;
            tmp.u=v;
            tmp.v=D[v];
            Q.push(tmp);
        }
    }
}
}

void Scanf(int &s){
char x;
while((x=getchar())<'0' || x>'9');
s=x-'0';
while((x=getchar())>='0' && x<='9')s=s*10+x-'0';
}

int main(){
freopen("1001.in","r",stdin);
freopen("1001.out","w",stdout);
Scanf(n);
Scanf(m);
S=0;
T=(n-1)*(m-1)*2+1;
memset(h,-1,sizeof(h));
en=0;
if(n==1 || m==1){
    n=max(n,m);
    int ans=2147483647,w;
    for(int i=1;i<n;i++){
        Scanf(w);
        ans=min(ans,w);
    }
    printf("%d\n",ans==2147483647?0:ans);
    return 0;
}
for(int i=0;i<=n-1;i++){
    for(int j=1;j<=m-1;j++){
        int sa,sb,sc;
        Scanf(sc);
        sa=((i-1)*(m-1)+j)*2-1;
        sb=(i*(m-1)+j)*2;
        if(i==0)sa=T;
        else if(i==n-1)sb=S;
        add(sa,sb,sc);
        add(sb,sa,sc);
    }
}
for(int i=1;i<=n-1;i++){
    for(int j=0;j<=m-1;j++){
        int sa,sb,sc;
        Scanf(sc);
        sa=((i-1)*(m-1)+j)*2;
        sb=((i-1)*(m-1)+j+1)*2-1;
        if(j==0)sa=S;
        else if(j==m-1)sb=T;
        add(sa,sb,sc);
        add(sb,sa,sc);
    }
}
for(int i=1;i<=n-1;i++){
    for(int j=1;j<=m-1;j++){
        int sa,sb,sc;
        Scanf(sc);
        sa=((i-1)*(m-1)+j)*2;
        sb=((i-1)*(m-1)+j)*2-1;
        add(sa,sb,sc);
        add(sb,sa,sc);
    }
}
Dijkstra();
return 0;
}