货物运输

NC220553. 货物运输

描述

运输公司提供了许多运输方案，每个方案 $P_i$ 会从一个固定的起始城市 $A_i$ 运送东西到另一个固定的终点城市 $B_i$ ，每运输一箱的货物，你就必须付给运输公司 $C_i$ 哒哒币。另外，若两个方案的终点与起点相接，则可以不花任何额外费用的将货物转过去。不过由于你的运输量太大了，运输公司决定祭出优惠，若用方案 $P_i$ 运输了超过 $D_i$ 箱的可鱼果，多出来的部份每箱改收优惠价 $C^,_i$ 哒哒币。

输入描述

输入的第一行有一个正整数  ，代表测试数据的组数。
每组测试数据的第一行有五个正整数 ，各一个空白隔开。

代表可鱼国内有几个城市， 代表墨鱼运输公司提供几种运输方 案。分别代表你的工厂所在的城市以及你所要送去的城市。代表那隻富有的大可鱼订购了多少箱的货物。

接下来 行，每行有五个正整数 ，意思如同叙述中所说。

输出描述

每组测试数据输出一行，表示最小的花费

示例1

输入:

3
4 4 1 4 1
1 2 1 1 1
2 4 5 1 3
1 3 1 1 1
3 4 6 1 1
4 4 1 4 2
1 2 1 1 1
2 4 5 1 3
1 3 1 1 1
3 4 6 1 1
2 1 1 2 999999999
1 2 50216 1000 50216

输出:

6
9
50215999949784

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 21ms, 内存消耗: 504K, 提交时间: 2021-04-27 20:18:07

#include <bits/stdc++.h>
using namespace std;
int t, n, m, s, e, a, b;
long long l[110][110], f, c, d, cc;
int main() {
	cin >> t;
	while (t--) {
		cin >> n >> m >> s >> e >> f;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				l[i][j] =  1e17;
		for (int i = 0; i < m; i++)
			cin >> a >> b >> c >> d >> cc, l[a][b] =  min(l[a][b],f>d?c*d+cc*(f-d):f*c);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				for (int k = 1; k <= n; k++)
					l[j][k] = min(l[j][k], l[j][i] + l[i][k]);
		cout << l[s][e] << endl;
	}
}

上一题

下一题

详情