社区讨论
我这怎么是最长路了?
P2299Mzc和体委的争夺战参与者 4已保存回复 31
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 31 条
- 当前快照
- 1 份
- 快照标识符
- @lo21sttu
- 此快照首次捕获于
- 2023/10/23 06:36 2 年前
- 此快照最后确认于
- 2023/11/03 06:58 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 1005, INF = 1e5 + 6;
vector <int> p[N], b[N];
queue <int> q;
int n, m, vis[N];
bool cmp[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
p[x].push_back(y);
b[x].push_back(z);
p[y].push_back(x);
b[y].push_back(z);
}
cmp[1] = true;
q.push(1);
int ans = INF;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int d = 0; d < p[u].size(); ++d) {
int nx = p[u][d];
if (!cmp[nx]) {
cmp[nx] = true;
vis[nx] = vis[u] + b[u][d];
if (nx == n)
ans = min (ans, vis[nx]);
q.push(nx);
}
}
}
printf("%d", ans);
return 0;
}
回复
共 31 条回复,欢迎继续交流。
正在加载回复...