聊城seo整站优化报价,wordpress 添加字段,做电商需要知道的几个网站吗,外国ps素材网站原题链接#xff1a;
PTA | 程序设计类实验辅助教学平台 题面#xff1a; 在一个名叫刀塔的国家里#xff0c;有一只猛犸正在到处跑着#xff0c;希望能够用它的长角抛物技能来撞飞别人。已知刀塔国有 N 座城市#xff0c;城市之间由 M 条道路互相连接#xff0c;为了拦…原题链接
PTA | 程序设计类实验辅助教学平台 题面 在一个名叫刀塔的国家里有一只猛犸正在到处跑着希望能够用它的长角抛物技能来撞飞别人。已知刀塔国有 N 座城市城市之间由 M 条道路互相连接为了拦住这头猛犸每条道路上设置了 Vi 人的团队。 这只猛犸从 S 号城市出发它可以选择 在不重复地经过若干条道路后回到 S 号城市在不重复地经过若干条道路后到达 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_queueedge 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;
}
