Problem: G - Revenge of Minimum Cost Flow

Problem Statement

Flora is a freelance carrier pigeon. Since she is an excellent pigeon, there are too much task requests to her. It is impossible to do all tasks, so she decided to outsource some tasks to Industrial Carrier Pigeon Company.

There are N cities numbered from 0 to N-1. The task she wants to outsource is carrying f freight units from city s to city t. There are M pigeons in the company. The i-th pigeon carries freight from city s_i to t_i, and carrying cost of u units is u a_i if u is smaller than or equals to d_i, otherwise d_i a_i + (u-d_i)b_i. Note that i-th pigeon cannot carry from city t_i to s_i. Each pigeon can carry any amount of freights. If the pigeon carried freight multiple times, the cost is calculated from total amount of freight units he/she carried.

Flora wants to minimize the total costs. Please calculate minimum cost for her.

Input

The test case starts with a line containing five integers N (2 \leq N \leq 100), M (1 \leq M \leq 1{,}000), s (0 \leq s \leq N-1), t (0 \leq t \leq N-1) and f (1 \leq f \leq 200). You may assume s \neq t. Each of the next M lines contains five integers s_i (0 \leq s_i \leq N-1), t_i (0 \leq t_i \leq N-1), a_i (0 \leq a_i \leq 1{,}000), b_i (0 \leq b_i \leq 1{,}000) and d_i (1 \leq d_i \leq 200). Each denotes i-th pigeon's information. You may assume at most one pair of a_i and b_i satisfies a_i < b_i, all others satisfies a_i > b_i.

Output

Print the minimum cost to carry f freight units from city s to city t in a line. If it is impossible to carry, print "Impossible" (quotes for clarity).

Sample Input 1


2 2 0 1 5
0 1 3 0 3
0 1 2 1 6


Output for the Sample Input 1


9


Sample Input 2


4 4 0 3 5
0 1 3 0 3
1 3 3 0 3
0 2 2 1 6
2 3 2 1 6


Output for the Sample Input 2


18


Sample Input 3


2 1 0 1 1
1 0 1 0 1


Output for the Sample Input 3


Impossible


Sample Input 4


2 2 0 1 2
0 1 5 1 2
0 1 6 3 1


Output for the Sample Input 4


9


Sample Input 5


3 3 0 2 4
0 2 3 4 2
0 1 4 1 3
1 2 3 1 1


Output for the Sample Input 5


14






Example

Input

2 2 0 1 5
0 1 3 0 3
0 1 2 1 6


Output

9

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 105

struct Edge{
	Edge(int arg_to,int arg_a,int arg_b,int arg_d){
		to = arg_to;
		a = arg_a;
		b = arg_b;
		d = arg_d;
		cost = BIG_NUM;
	}
	int to,a,b,d,cost;
};

struct State{
	State(int arg_node_id,int arg_sum_dist){

		node_id = arg_node_id;
		sum_dist = arg_sum_dist;

	}
	bool operator<(const struct State &arg) const{

		return sum_dist > arg.sum_dist; //総距離の降順(PQ)
	}

	int node_id,sum_dist;
};

int V,E;
int start,goal;
int FROM,TO;
int FLOW;
int min_dist[NUM];
int table_1[NUM][NUM],table_2[NUM][NUM],table_3[NUM][NUM];
vector<Edge> G[NUM];


void dijkstra(){

	//コストを計算する
	for(int i = 0; i < V; i++){
		for(int k = 0; k < G[i].size(); k++){

			if(FLOW <= G[i][k].d){

				G[i][k].cost = G[i][k].a*FLOW;

			}else{

				G[i][k].cost = (FLOW-G[i][k].d)*G[i][k].b+G[i][k].a*G[i][k].d;
			}
		}
	}

	for(int i = 0; i < V; i++){

		min_dist[i] = BIG_NUM;
	}

	min_dist[start] = 0;
	priority_queue<State> Q;

	Q.push(State(start,0));

	while(!Q.empty()){

		if(Q.top().sum_dist > min_dist[Q.top().node_id]){

			Q.pop();

		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){

				int next_node = G[Q.top().node_id][i].to;
				int next_cost = Q.top().sum_dist+G[Q.top().node_id][i].cost;

				if(min_dist[next_node] > next_cost){

					min_dist[next_node] = next_cost;
					Q.push(State(next_node,next_cost));
				}
			}

			Q.pop();
		}
	}
}

void init(int table[NUM][NUM]){

	for(int i = 0; i < V; i++){
		for(int k = 0; k < V; k++){
			if(k != i){
				table[i][k] = BIG_NUM;
			}else{
				table[i][k] = 0;
			}
		}
	}
}

void calc_cost(int table[NUM][NUM],int base_flow,int table_index){

	for(int i = 0; i < V; i++){
		for(int k = 0; k < G[i].size(); k++){

			int cost;

			if(base_flow <= G[i][k].d){

				cost = G[i][k].a*base_flow;

			}else{

				cost = (base_flow-G[i][k].d)*G[i][k].b+G[i][k].a*G[i][k].d;
			}

			if(i == FROM && G[i][k].to == TO){

				if(table_index == 2){ //a < bとなっている辺には流さない

					if(G[i][k].a < G[i][k].b){

						cost = BIG_NUM;
					}

				}else if(table_index == 3){ //a < bとなっている辺に流す

					if(G[i][k].a > G[i][k].b){

						cost = BIG_NUM;
					}
				}

			}

			table[i][G[i][k].to] = min(table[i][G[i][k].to],cost);
		}
	}
}

void warshall_floyd(int table[NUM][NUM]){

	for(int mid = 0; mid < V; mid++){
		for(int L = 0; L < V; L++){
			if(table[L][mid] == BIG_NUM)continue;
			for(int R = 0; R < V; R++){
				if(table[mid][R] == BIG_NUM)continue;

				table[L][R] = min(table[L][R],table[L][mid]+table[mid][R]);
			}
		}
	}
}

int main(){

	scanf("%d %d %d %d %d",&V,&E,&start,&goal,&FLOW);

	bool FLG = false;

	int from,to,a,b,d;


	for(int loop = 0; loop < E; loop++){

		scanf("%d %d %d %d %d",&from,&to,&a,&b,&d);

		if(a < b){

			FLG = true;
			FROM = from;
			TO = to;
		}

		G[from].push_back(Edge(to,a,b,d));
	}

	dijkstra();

	if(!FLG){

		if(min_dist[goal] == BIG_NUM){

			printf("Impossible\n");

		}else{

			printf("%d\n",min_dist[goal]);
		}

		return 0;
	}

	//経路を分岐させる
	int ans = min_dist[goal];

	//FLOW流した場合のテーブル作成
	init(table_1);
	calc_cost(table_1,FLOW,1);
	warshall_floyd(table_1);

	for(int flow = 1; flow <= FLOW-1; flow++){ //流す配分を全通り試す:flow→a < bとなる辺に流す流量

		//FLOW-flow流した場合のテーブル作成
		init(table_2);
		calc_cost(table_2,FLOW-flow,2);
		warshall_floyd(table_2);


		//flow流した場合のテーブル作成
		init(table_3);
		calc_cost(table_3,flow,3);
		warshall_floyd(table_3);

		//分岐を全探索
		for(int mid_L = 0; mid_L < V; mid_L++){
			for(int mid_R = 0; mid_R < V; mid_R++){

				int cost_1 = table_1[start][mid_L];
				int cost_2 = table_2[mid_L][mid_R];
				int cost_3 = table_3[mid_L][mid_R];
				int cost_4 = table_1[mid_R][goal];

				if(cost_1 == BIG_NUM || cost_2 == BIG_NUM || cost_3 == BIG_NUM || cost_4 == BIG_NUM)continue;

				ans = min(ans,cost_1+cost_2+cost_3+cost_4);
			}
		}
	}

	if(ans == BIG_NUM){

		printf("Impossible\n");

	}else{

		printf("%d\n",ans);
	}

	return 0;
}