题解 - Vijos

1

Pia LV 9 @ 2016-08-08 11:24:26

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 500000 + 5;
const int INF = 1000000000;

int n, l[10][505][505];

struct Edge {
    int from, to, dist;
    Edge (int from, int to, int dist) : from(from), to(to), dist(dist) {}
};
struct HeapNode {
    int d, u;
    HeapNode (int d, int u) : d(d), u(u) {}
    bool operator < (const HeapNode& rhs) const {
        return d > rhs.d;
    }
};

struct Dijkstra{
    int n, m, d[maxn],G[250001][100],size[maxn];
    vector<Edge> edges;
    bool done[maxn];
    
    void init(int n){
        this -> n = n;
        m = 0;
        memset(d, 0, sizeof(d));
        memset(G, 0, sizeof(G));
        edges.clear();
        memset(size, 0, sizeof(size));
    }
    
    void AddEdge(int from, int to, int dist){
        edges.push_back(Edge{from, to, dist});
        G[from][size[from]++] = m++;
        
    }
    
    void dijkstra(int s){
        priority_queue<HeapNode> Q;
        for(int i = 0; i < n; i++) d[i] = INF;
        d[s] = 0;
        memset(done, 0, sizeof(done));
        Q.push(HeapNode{0,s});
        while(!Q.empty()){
            HeapNode x = Q.top(); Q.pop();
            int u = x.u;
            if(done[u]) continue;
            done[u] = 1;
            for(int i = 0; i < size[u]; i++){
                Edge& e = edges[G[u][i]];
                if(d[e.to] > d[u] + e.dist){
                    d[e.to] = d[u] + e.dist;
                    Q.push(HeapNode{d[e.to], e.to});
                }
            }
        }
    }
};
Dijkstra solver;

int cnt;
int id[550][550];
int ID (int i, int j) {
    int& x = id[i][j];
    if (x == 0) x = ++cnt;
    return x;
}

void init(){
    cin >> n;
    for(int k = 0; k < 4; k++)
        for(int i = 0; i < n+(k+1)%2; i++)
            for(int j = 0; j < n+k%2; j++)
                cin >> l[k][i][j];
    solver.init(n*n+2);
    cnt = 0;
    memset(id, 0, sizeof(id));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++){
            int idx = ID(i,j);
            if(j > 0) solver.AddEdge(idx,ID(i,j-1),l[3][i][j]);
            if(j < n-1) solver.AddEdge(idx,ID(i,j+1),l[1][i][j+1]);
            if(i > 0) solver.AddEdge(idx,ID(i-1,j),l[0][i][j]);
            if(i < n-1) solver.AddEdge(idx,ID(i+1,j),l[2][i+1][j]);
        }
    for(int i = 0; i < n; i++){
            solver.AddEdge(0,ID(i,0),l[1][i][0]);
            solver.AddEdge(0,ID(n-1,i),l[0][n][i]);
            solver.AddEdge(ID(0,i),cnt+1,l[0][0][i]);
            solver.AddEdge(ID(i,n-1),cnt+1,l[1][i][n]);
    }
    

}

int main(){
    init();
    solver.dijkstra(0);
    cout << solver.d[cnt+1];
    
    return 0;
}

0

caesar_199 LV 9 @ 2016-08-08 08:29:16

2006年ACM北京的一道题，不过那边是一个三角形一个结点
```c++
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

const int INF = 1000000000;
const int maxsize = 500 + 10;
const int maxn = 500 * 500 + 100;

struct Edge {
int from, to, dist;
Edge (int from, int to, int dist) : from(from), to(to), dist(dist) {}
};

struct HeapNode {
int d, u;
HeapNode (int d, int u) : d(d), u(u) {}
bool operator < (const HeapNode& rhs) const {
return d > rhs.d;
}
};

struct Dijkstra {
int n, m;
vector<int> G[maxn];
vector<Edge> edges;
int d[maxn], p[maxn];
bool done[maxn];

void init (int n) {
this->n = n;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
}

void AddEdge (int from, int to, int dist) {
edges.push_back(Edge(from, to, dist));
m = edges.size();
G[from].push_back(m-1);
}

void dijkstra (int s) {
priority_queue<HeapNode> Q;
memset(done, 0, sizeof(done));
for (int i = 0; i < n; i++) d[i] = INF;
d[s] = 0;
Q.push(HeapNode(d[s], s));
while (!Q.empty()) {
HeapNode x = Q.top(); Q.pop();
int u = x.u;
if (done[u]) continue;
done[u] = true;
for (int i = 0; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
if (d[e.to] > d[u] + e.dist) {
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push(HeapNode(d[e.to], e.to));
}
}
}
}
};

Dijkstra solver;

int cnt;
int id[maxsize][maxsize];
int ID (int i, int j) {
int& x = id[i][j];
if (x == 0) x = ++cnt;
return x;
}

int n;
int flow[maxsize][maxsize][4];

int main ()
{
// freopen("in.txt", "r", stdin);
cin >> n;
n++;
solver.init((n-1)*(n-1)+2);
for (int i = 0; i < n; i++) for (int j = 0; j < n-1; j++) scanf("%d", &flow[i][j][0]); //right
for (int i = 0; i < n-1; i++) for (int j = 0; j < n; j++) scanf("%d", &flow[i][j][1]); //down
for (int i = 0; i < n; i++) for (int j = 0; j < n-1; j++) scanf("%d", &flow[i][j][2]); //left
for (int i = 0; i < n-1; i++) for (int j = 0; j < n; j++) scanf("%d", &flow[i][j][3]); //up

cnt = 0;
memset(id, 0, sizeof(id));
for (int i = 0; i < n-1; i++) for (int j = 0; j < n-1; j++) {
int idn = ID(i, j);
if (i > 0) solver.AddEdge(idn, ID(i-1, j), flow[i][j][0]);
if (i < n-2) solver.AddEdge(idn, ID(i+1, j), flow[i+1][j][2]);

if (j > 0) solver.AddEdge(idn, ID(i, j-1), flow[i][j][3]);
if (j < n-2) solver.AddEdge(idn, ID(i, j+1), flow[i][j+1][1]);
}

for (int i = 0; i < n-1; i++) {
solver.AddEdge(0, ID(i, 0), flow[i][0][1]);
solver.AddEdge(0, ID(n-2, i), flow[n-1][i][0]);

solver.AddEdge(ID(0, i), cnt+1, flow[0][i][0]);
solver.AddEdge(ID(i, n-2), cnt+1, flow[i][n-1][1]);
}

solver.dijkstra(0);
cout << solver.d[cnt+1];

return 0;
}
```

0

疯-神 LV 8 @ 2015-07-01 10:40:56

AC

const maxn=2000000;
type node=record
from,go,next,w:longint;
end;
var i,j,n,cnt,tot,t,x,s,l,r,y:longint;
head,d,a,p:array[0..maxn] of longint;
v:array[0..maxn] of boolean;
e:array[0..maxn] of node;
num:array[0..600,0..600] of longint;
procedure insert(x,y,z:longint);
begin
inc(tot);
e[tot].from:=x;e[tot].go:=y;e[tot].w:=z;e[tot].next:=head[x];head[x]:=tot;
end;
procedure up(i:longint);
var t:longint;
begin
while (i>1) and (d[a[i]]<d[a[i>>1]]) do
begin
t:=a[i];a[i]:=a[i>>1];a[i>>1]:=t;
p[a[i]]:=i;p[a[i>>1]]:=i>>1;
i:=i>>1;
end;
end;
procedure down(i:longint);
var t,j:longint;
begin
j:=i<<1;
if (j<cnt) and (d[a[j+1]]<d[a[j]]) then inc(j);
while (j<=cnt) and (d[a[j]]<d[a[i]]) do
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
p[a[i]]:=i;p[a[j]]:=j;
i:=j;j:=j<<1;
if (j<cnt) and (d[a[j+1]]<d[a[j]]) then inc(j);
end;
end;
procedure dijkstra;
begin
fillchar(d,sizeof(d),60);
fillchar(v,sizeof(v),false);
d[s]:=0;cnt:=0;
for i:=0 to n*n+1 do begin inc(cnt);a[cnt]:=i;p[i]:=cnt;up(cnt);end;
for j:=1 to n*n+1 do
begin
x:=a[1];a[1]:=a[cnt];dec(cnt);down(1);
v[x]:=true;
i:=head[x];
while i<>0 do
begin
y:=e[i].go;
if not(v[y]) and (d[x]+e[i].w<d[y]) then
begin
d[y]:=d[x]+e[i].w;
up(p[y]);
end;
i:=e[i].next;
end;
end;
end;
procedure init;
begin
readln(n);s:=0;t:=n*n+1;
for i:=1 to n do for j:=1 to n do num[i,j]:=(i-1)*n+j;
for i:=1 to n+1 do
for j:=1 to n do
begin
readln(x);
if i=1 then insert(num[i,j],t,x)
else if i=n+1 then insert(s,num[i-1,j],x)
else insert(num[i,j],num[i-1,j],x);
end;
for i:=1 to n do
for j:=1 to n+1 do
begin
readln(x);
if j=1 then insert(s,num[i,j],x)
else if j=n+1 then insert(num[i,j-1],t,x)
else insert(num[i,j-1],num[i,j],x);
end;
for i:=1 to n+1 do
for j:=1 to n do
begin
readln(x);
if i=1 then insert(t,num[i,j],x)
else if i=n+1 then insert(num[i-1,j],s,x)
else insert(num[i-1,j],num[i,j],x);
end;
for i:=1 to n do
for j:=1 to n+1 do
begin
readln(x);
if j=1 then insert(num[i,j],s,x)
else if j=n+1 then insert(t,num[i,j-1],x)
else insert(num[i,j],num[i,j-1],x);
end;
end;
procedure main;
begin
dijkstra;
writeln(d[t]);
end;
begin
init;
main;
end.

cenbinbin @ 2015-07-01 10:41:45

hello！
疯-神 @ 2015-07-01 10:42:57

猪再脑残一次给我试试

0

lcy1996 LV 8 @ 2014-06-12 11:06:08

写spfa其实只要加上 if(dis[p]+side[i].c>dis[T] && dis[T]!=-1) continue;
这句优化就可以过了（如果常数比较正常的话）

0

EC-Ecstasy LV 10 @ 2014-06-03 13:50:17

Binary Heap的dijkstra果然还是比lll+slf的spfa快一吨的速度

0

freefood LV 10 @ 2014-06-02 21:29:02

http://hi.baidu.com/macaulish64/item/a37478d164ee0ac03cc2cb25

0

fshp971 LV 10 @ 2014-02-16 16:31:07

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 49620 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 49616 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 49616 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 49616 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 49616 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 49620 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 49616 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 49612 KiB, score = 10
测试数据 #8: Accepted, time = 452 ms, mem = 49616 KiB, score = 10
测试数据 #9: Accepted, time = 374 ms, mem = 49620 KiB, score = 10
Accepted, time = 826 ms, mem = 49620 KiB, score = 100
代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

const long long inf=(long long)1<<40;
const int maxn=500+10;

struct Tree
{
long long dis;
int tp;
}tree[maxn*maxn*2];

struct node
{
int to,flow,mf;
}edge[maxn*maxn*4*2];

long long dans[maxn*maxn*2];
int wh[maxn*maxn*2];
int n,h[maxn*maxn],nex[maxn*maxn*4*2];
int top=-1,dis[maxn*maxn],tail;
int tt,ss;

void tree_swap(Tree& a,Tree& b)
{
Tree c=a; a=b; b=c;
return;
}

int rm(int x,int y)
{
if(x>n||y<1) return ss;
if(x<1||y>n) return tt;
return n*(y-1)+x;
}

void addedge(int x,int y,int flow)
{
edge[++top]=(node){y,0,flow};
nex[top]=h[x]; h[x]=top;
return;
}

void init(void)
{
cin>>n;
memset(h,-1,sizeof(h));
int flow;
ss=0; tt=rm(n,n)+1;
for(int i=1;i<=n+1;++i)
{
for(int k=1;k<=n;++k)
{
scanf("%d",&flow);
addedge(rm(i,k),rm(i-1,k),flow);
}
}
for(int i=1;i<=n;++i)
{
for(int k=1;k<=n+1;++k)
{
scanf("%d",&flow);
addedge(rm(i,k-1),rm(i,k),flow);
}
}
for(int i=1;i<=n+1;++i)
{
for(int k=2;k<=n+1;++k)
{
scanf("%d",&flow);
addedge(rm(i-1,k-1),rm(i,k-1),flow);
}
}
for(int i=2;i<=n+1;++i)
{
for(int k=1;k<=n+1;++k)
{
scanf("%d",&flow);
addedge(rm(i-1,k),rm(i-1,k-1),flow);
}
}
return;
}

void up(int x)
{
while(x>1)
{
int k=x/2;
if(tree[k].dis>tree[x].dis)
{
wh[tree[k].tp]=x;
wh[tree[x].tp]=k;
tree_swap(tree[k],tree[x]);
x=k;
}
else break;
}
return;
}

void down(int x)
{
while(x<=(tail/2))
{
int k=x*2;
if(k+1<=tail&&tree[k+1].dis<tree[k].dis) ++k;
if(tree[k].dis<tree[x].dis)
{
wh[tree[k].tp]=x;
wh[tree[x].tp]=k;
tree_swap(tree[k],tree[x]);
x=k;
}
else break;
}
return;
}

void dja(void)
{
bool vis[maxn*maxn*2];
memset(vis,0,sizeof(vis));
for(int i=1;i<=tt+1;++i)
{
tree[i].dis=inf;
tree[i].tp=i-1;
wh[i-1]=i;
}
tail=tt+1;
tree[1].dis=0;
for(int i=1;i<=tt+1;++i)
{
Tree now=tree[1];
vis[now.tp]=true; dans[now.tp]=now.dis;
int k=h[now.tp];
while(k!=-1)
{
node e=edge[k];
if(vis[e.to]==false&&tree[wh[e.to]].dis>e.mf+now.dis)
{
tree[wh[e.to]].dis=e.mf+now.dis;
up(wh[e.to]);
}
k=nex[k];
}
tree[1]=tree[tail--];
down(1);
}
cout<<dans[tt];
return;
}

int main(void)
{
init();
dja();
return 0;
}

0

fshp971 LV 10 @ 2014-02-16 16:29:42

###Block code
编译成功