2021 Robocom 决赛 第四题

原题链接：

PTA | 程序设计类实验辅助教学平台

题面：

在一个名叫刀塔的国家里，有一只猛犸正在到处跑着，希望能够用它的长角抛物技能来撞飞别人。已知刀塔国有 N 座城市，城市之间由 M 条道路互相连接，为了拦住这头猛犸，每条道路上设置了 Vi​ 人的团队。

这只猛犸从 S 号城市出发，它可以选择：

1. 在不重复地经过若干条道路后回到 S 号城市；
2. 在不重复地经过若干条道路后到达 T 号城市。

猛犸经过一条道路后，就会把路上的人全部撞飞。作为一头爱喝雪碧的仁慈的猛犸，自然希望尽可能的少撞飞人。请你帮忙计算一下在最优的选择下，最少需要撞飞多少人才能够到达目标城市？

输入格式:

输入第一行是四个正整数 N,M,S,T (2≤N≤500,1≤M≤105)，表示有 N 个城市，M 条道路，猛犸从 S 号城市出发，可以选择到达 T 号城市。

接下来的 M 行，每行三个正整数 Xi​,Yi​,Vi​ (0≤Vi​≤100)，表示从 Xi​ 号城市到 Yi​ 号城市有一条道路，道路上有 Vi​ 人的团队。道路可双向通行，城市编号从 1 开始，两个城市之间最多只有一条道路，且没有一条道路连接相同的城市。

数据保证两种选择里至少有一种是可行的。

输出格式:

输出两行，第一行是两个数字，分别对应上面的两种选择分别最少需要撞飞多少人。如果无论撞飞多少人都无法满足选择要求，则输出 -1。

第二行是一个句子，如果第一种（回到原点）的选择比较好，就输出 Win!，否则输出Lose!。

输入样例:

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

输出样例:

在这里给出相应的输出。例如：

11 6
Lose!

解题思路：

第二种方式直接跑dijkstra，计算出d[]，d[t]即为答案。对于第一种方式，不难想到，最终得到的结果其实就是从s到某个点i的最短路，这个点i必须是与起点s直接存在一条相连的边，然后再从i直接到s，即d[i] + G[s][i] (1 <= i <= n)。但需要注意的是，我们在枚举i时应该重跑dijkstra，并且将s->i这条边暂时删除，不然得出的结果就是s->i->s。

代码（CPP）：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1000000007;
struct edge {int v, w;bool operator < (const edge &other) const {return w > other.w;}
};
int G[maxn][maxn];
int d[maxn];
bool vis[maxn];
int n, m, s, t;void dijkstra() {memset(vis, 0, sizeof vis);fill(d, d + maxn, INF);d[s] = 0;priority_queue<edge> q;q.push({s, 0});while (!q.empty()) {int u = q.top().v;q.pop();if (vis[u]) {continue;}vis[u] = true;for (int v = 1; v <= n; v++) {if (G[u][v] != INF && !vis[v] && d[u] + G[u][v] < d[v]) {d[v] = d[u] + G[u][v];q.push({v, d[v]});}}}
}void solve() {cin >> n >> m >> s >> t;fill(G[0], G[0] + maxn * maxn, INF);while (m--) {int u, v, w;cin >> u >> v >> w;G[u][v] = G[v][u] = w;}// 第二种方式dijkstra();int ans2 = d[t];// 第一种方式int ans1 = INF;for (int i = 1; i <= n; i++) {if (s == i || G[i][s] == INF)continue;G[s][i] = INF;  // 要把直接从s到i的边删除，再计算dijkstradijkstra();ans1 = min(ans1, d[i] + G[i][s]);G[s][i] = G[i][s];}cout << (ans1 == INF ? -1 : ans1) << " " << (ans2 == INF ? -1 : ans2) << endl;if (ans1 < ans2)cout << "Win!";elsecout << "Lose!";
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout << fixed;cout.precision(18);solve();return 0;
}