acwing 851. spfa求最短路
标签：targe ack thml else empty pac com desc math
地址 https://www.acwing.com/problem/content/description/853/
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出”impossible”。
数据范围
1≤n,m≤1051≤n,m≤105,
图中涉及边长绝对值均不超过10000。
输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2
解答
#include
#include
#include
#include
#include using namespace std;
/* acwing 851
3 3
1 2 5
2 3 -3
1 3 4
*/
const int MAX_N = 100010;
vectorint, int>> v[MAX_N];
int dist[MAX_N];
int st[MAX_N];
int n, m;
int solve()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
queueint> q;
q.push(1);
st[1] = 1;
while (!q.empty()) {
auto e = q.front();
q.pop();
st[e] = false;
for (int i = 0; i ) {
int target = v[e][i].first;
int len = v[e][i].second;
if (dist[target] > dist[e] + len) {
dist[target] = dist[e] + len;
if (!st[target]) {
//队列中不存在target节点 插入队列
q.push(target);
st[target] = 1;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
//cin >> n >> m;
scanf("%d%d",&n,&m);
//v.resize(n+1);
for (int i = 0; i ) {
int a, b, c;
//cin >> a >> b >> c;
scanf("%d%d%d",&a,&b,&c);
v[a].push_back({ b,c });
}
int ret = solve();
if (ret == -1) printf("impossible\n");
else printf("%d\n",dist[n]);
return 0;
}
acwing 851. spfa求最短路
标签：targe ack thml else empty pac com desc math
原文地址：https://www.cnblogs.com/itdef/p/12054430.html
评论