记录编号	389993	评测结果	AAAAAAAAAA
题目名称	13.运输问题4	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-04-01 13:40:26	内存使用	0.00 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

#define is_num(tmp) (tmp<='9' and tmp>='0')
#define MAXN 110
#define INF 0x7fffffff

const inline int in(void){
	char tmp = getchar();
	int res = 0;
	while(!is_num(tmp))tmp = getchar();
	while(is_num(tmp))
		res = (res<<1) + (res<<3) + (tmp^48),
		tmp = getchar();
	return res;
}

class FLOW{
private:
	struct EDGE{
		int fr, to, ne, v, w;
		
		EDGE(){;}
		EDGE(const int& _fr, const int& a, const int& b, const int& c, const int& d){
			fr = _fr, to = a, ne = b, v = c, w = d;
		}
	};
	EDGE edge[MAXN*MAXN*2];
	int head[MAXN], tot;
	const inline void add_edge(const int& fr, const int& to, const int& v, const int& w){
		edge[++tot] = EDGE(fr, to, head[fr], v, w), head[fr] = tot;
		edge[++tot] = EDGE(to, fr, head[to], 0, -w), head[to] = tot;
		return ;
	}
	
	int S, T, N;
	int pre[MAXN];
	int dis[MAXN];
	bool exist[MAXN];
	int max_flow, min_cost;
	queue<int>que;
	
	const inline void get_map(void){
		N = in(), S = in(), T = in();
		int a, b;
		
		for(int i = 1; i <= N; ++i){
			for(int j = 1; j <= N; ++j){
				a = in(), b = in();
				if(!a)continue;
				add_edge(i, j, a, b);
			}
		}
		
		return ;
		
	}
	
	const inline bool SPFA(void){
		memset(exist, false, sizeof(exist));
		memset(dis, 0x7f, sizeof(dis));
		memset(pre, 0, sizeof(pre));
		while(!que.empty())que.pop();
		
		exist[S] = true;
		dis[S] = 0;
		que.push(S);
		
		int now, to;
		
		while(!que.empty()){
			now = que.front();
			exist[now] = false;
			que.pop();
			for(int i = head[now]; i; i = edge[i].ne){
				if(edge[i].v <= 0)continue;
				to = edge[i].to;
				if(dis[now] + edge[i].w < dis[to]){
					dis[to] = dis[now] + edge[i].w;
					pre[to] = i;
					if(!exist[to]){
						exist[to] = true;
						que.push(to);
					}
				}
			}
		}
		
		if(dis[T] == 0x7f7f7f7f)return false;
		else return true;
	}
	
	const inline int get_flow(void){
		int res = INF;
		int now = pre[T];
		while(pre[edge[now].to]){
			res = min(res, edge[now].v);
			now = pre[edge[now].fr];
		}
		now = pre[T];
		while(pre[edge[now].to]){
			edge[now].v -= res;
			if(now&1)edge[now+1].v += res;
			else edge[now-1].v += res;
			now = pre[edge[now].fr];
		}
		if(res == INF)return 0;
		else return res;
	}
	
	const inline int get_cost(){
		int res = 0;
		for(int i = 1; i <= tot; i+=2){
			if(edge[i+1].v > 0)res += edge[i].w * edge[i+1].v;
		}
		return res;
	}
public:
	
	void work(void){
		get_map();
		while(SPFA()){
			max_flow += get_flow();
		}
		min_cost = get_cost();
		return ;
	}
	
	void print(void){
		printf("%d", min_cost);
		return ;
	}
};

FLOW a;

void *Main(){
#ifndef LOCAL
	freopen("maxflowd.in", "r", stdin);
	freopen("maxflowd.out", "w", stdout);
#endif
	a.work();
	a.print();
	
	return NULL;
}
void  *Main_(Main());
int main(){;}