记录编号	338576	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]海拔	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.591 s
提交时间	2016-11-05 11:49:47	内存使用	65.22 MiB

//平面图网络流 --> 对偶图最短路
//Orz Mike
//对偶图建图始终是个坑...
#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <ext/pb_ds/priority_queue.hpp>
#include <algorithm>
#include <list>
#include <vector>
using namespace std;
#define MAXN 2001
struct edge
{
    int to, dist;
};
vector<int> G[MAXN*MAXN];
vector<edge> edges;
void adde(int u, int v)
{
    int d;
    scanf("%d", &d);
    edges.push_back((edge){v, d});
    int k = edges.size();
    G[u].push_back(k-1);
}
struct heap_node
{
    int u, d;
    bool operator<(const heap_node &od)const
    {
        return d > od.d;
    }
};
int n;
int s, t;
inline int pt2id(int x, int y)
{
    if(!x||y>n)return t;
    if(!y||x>n)return s;
    return (x-1)*n+y;
}
int dist[MAXN*MAXN];
bool done[MAXN*MAXN];
int dijkstra()
{
    for(int i = s; i <= t; i++)
    {
        done[i] = false;
        dist[i] = 0x3f3f3f3f;
    }
    dist[s] = 0;
    __gnu_pbds::priority_queue<heap_node> q;
    q.push((heap_node){s, 0});
    while(!q.empty())
    {
        heap_node d = q.top();
        q.pop();
        int u = d.u;
        if(done[u])continue;
        done[u] = true;
        if(u == t)break;
        for(int i = 0; i < G[u].size(); i++)
        {
            edge &e = edges[G[u][i]];
            if(dist[e.to] > dist[u] + e.dist)
            {
                dist[e.to] = dist[u] + e.dist;
                q.push((heap_node){e.to, dist[e.to]});
            }
        }
    }
    return dist[t];
}
int main()
{
    freopen("altitude.in", "r", stdin);
    freopen("altitude.out", "w", stdout);
    scanf("%d", &n);
    s = 0, t = n*n+1;
    for(int i = 0; i <= n; i++)for(int j = 1; j <= n; j++)adde(pt2id(i+1, j), pt2id(i, j));
    for(int i = 1; i <= n; i++)for(int j = 0; j <= n; j++)adde(pt2id(i, j), pt2id(i, j+1));
    for(int i = 0; i <= n; i++)for(int j = 1; j <= n; j++)adde(pt2id(i, j), pt2id(i+1, j));
    for(int i = 1; i <= n; i++)for(int j = 0; j <= n; j++)adde(pt2id(i, j+1), pt2id(i, j));
    printf("%d\n", dijkstra());
    return 0;
}