【小码匠自习室】我的目标去哪了？
我的目标去哪了？
昨晚开森AC了ABC 286 - E - Souvenir，小开森。。。
假期过半了，距离最初假期目标还有差距, 熟悉了下面相关算法，并刷了相关题目
- 位运算
- 并查集
- 最短路：dijkstra和floyd
还有
- 最短路：Bellman-Ford和SPFA
- 生成树
- 线段树、树状数组
- 组合数学
鸭梨山大。。。
欺负小孩没商量，我要找老码农谈判，机器人小码匠要濒临崩溃了。。。
题目
- E - Souvenir
- https://atcoder.jp/contests/abc286/tasks/abc286_e
有N个城市。还有连接不同城市的单程直达航班。
直飞航班的可用性由N个字符串
表示，每个字符串长度为N。如果S
的第j个字符是Y，则有从城市i到城市j的直达航班；如果是N，则不存在。
每个城市都出售一件纪念品；城市i出售价值a
的纪念品。
考虑以下问题：
高桥目前在S市，希望通过一些直飞航班到达T市（与S市不同）。 每次他访问一个城市（包括S和T），他都会在那里购买纪念品。 如果从S市到T市有多条路线，高桥决定路线如下：
- 他试图尽量减少从S市到T市的直达航班数量。
- 然后，他试图使他购买的纪念品的总价值最大化。
确定他是否可以使用直飞航班从S市前往T市。如果可以，请在满足上述条件的路线中查找“直飞航班数量”和“纪念品总价值”。
您将获得不同城市的Q对
。
对于每个
，当
和
时，打印上述问题的答案.
Constraints
是由Y和N组成的长度为N的字符串。
- The i-th character of
is N.
- If i
, then
.
和
都是整数。
输入
- N
- A
A
A
- S
- S
- S
- Q
- U
V
- U
V
- U
V
输出
打印Q行。
如果他不能从城市U
出发，第i行（
）应包含Impossible 至城市V
; 如果可以的话，该行应该包含“直飞航班的数量”和“纪念品的总价值”，按照上述顺序，用空格隔开。
示例输入 1
5
30 50 70 20 60
NYYNN
NNYNN
NNNYY
YNNNN
YNNNN
3
1 3
3 1
4 5
示例输出 1
1 100
2 160
3 180
对于
，有一个从城市1到城市3的直飞航班，因此直飞航班的最小可能数量为1，这是在他使用该直飞航班时实现的。在这种情况下，纪念品的总价值为
。
对于
，直飞航班的最小可能数量为2。以下两条路线达到最低要求：城市，
城市。由
于两条路线的纪念品总价值分别为70+20+30=120和70+60+30=160，因此他选择了后一条路线，纪念品总价值为160。
对于
，当他旅行城市时
，直飞航班的数量最少，其中纪念品的总价值为20+30+70+60=180。
示例输入 2
2
100 100
NN
NN
1
1 2
示例输出2
Impossible
可能根本没有直飞航班。
小码匠
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
void best_coder() {
int n;
cin >> n;
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
}
int INF = 1e9;
vector<vector<int>> g(n, vector<int>(n, INF));
vector<vector<long long>> dp(n, vector<long long>(n, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
char a;
cin >> a;
if (a == 'Y') {
g[i][j] = 1;
dp[i][j] = v[i] + v[j];
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (j == i) {
continue;
}
for (int s = 0; s < n; ++s) {
if (s == i || s == j) {
continue;
}
if (g[i][s] + g[j][i] < g[j][s]) {
dp[j][s] = dp[i][s] + dp[j][i] - v[i];
g[j][s] = g[i][s] + g[j][i];
} else if (g[i][s] + g[j][i] == g[j][s]){
dp[j][s] = max(dp[i][s] + dp[j][i] - v[i], dp[j][s]);
}
}
}
}
int m;
cin >> m;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
--a;
--b;
if (g[a][b] == INF) {
cout << "Impossible" << endl;
continue;
}
cout << g[a][b] << " " << dp[a][b] << endl;
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
腾讯云开发者
