acwing 853. 有边数限制的最短路 模板
标签：一个 imp www ssi clu preview 整数 fir ram
地址 https://www.acwing.com/problem/content/description/855/
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数n，m，k。
接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。
如果不存在满足条件的路径，则输出“impossible”。
数据范围
1≤n,k≤5001≤n,k≤500,
1≤m≤100001≤m≤10000,
任意边长的绝对值不超过10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3
解法
#include
#include
#include using namespace std;
const int N = 510;
vectorint, int>>> v;
int dist[N];
int back[N];
int n, m, k;
/*
3 3 1
1 2 1
2 3 1
1 3 3
*/
void solveInner(int back[])
{
for (int i = 0; i ) {
for (int j = 0; j ) {
int a = i; int b = v[i][j].first; int w = v[i][j].second;
if (dist[b] > back[a] + w) {
dist[b] = back[a] + w;
}
}
}
}
int solve()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
//进行n轮
for (int i = 0; i ) {
memcpy(back, dist, sizeof dist);
solveInner(back);
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
//cin >> n >> m >> k;
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");
else printf("%d\n",ret);
return 0;
}
acwing 853. 有边数限制的最短路 模板
标签：一个 imp www ssi clu preview 整数 fir ram
原文地址：https://www.cnblogs.com/itdef/p/12053690.html
评论