本文主要是介绍uva 10269 最短路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
求两次最短路
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#define maxn 105
#define INF 0x7fffffff
#define inf 10000000
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
using namespace std;int A, B, M, L, K, g[maxn][maxn];
int d[maxn][12];
bool inq[maxn][12];struct node
{int now, s;node(int i, int j){now = i, s = j;}
};void init()
{for(int i = 0; i < maxn; ++ i)for(int j = 0; j < maxn; ++ j) g[i][j] = inf;
}void floyd()
{for(int k = 1; k <= A; ++ k)for(int i = 1; i <= A+B; ++ i)for(int j = 1; j <= A+B; ++ j)if(g[i][k] != inf && g[k][j] != inf)g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
}int spfa()
{for(int i = 0; i <= A+B; ++ i)for(int j = 0; j <= K; ++ j)d[i][j] = inf;memset(inq, 0, sizeof(inq));queue<node> q;d[A+B][0] = 0;q.push(node(A+B, 0));while(!q.empty()){node t = q.front();q.pop();int u = t.now, k = t.s;inq[u][k] = false;for(int i = 1; i <= A+B; ++ i){if(i == u) continue;if(k < K && g[u][i] <= L){if(d[i][k+1] > d[u][k]){d[i][k+1] = d[u][k];if(!inq[i][k+1]){inq[i][k+1] = true;q.push(node(i, k+1));}}}if(d[i][k] > d[u][k]+g[u][i]){d[i][k] = d[u][k]+g[u][i];if(!inq[i][k]){inq[i][k] = true;q.push(node(i,k));}}}}int ans = inf;for(int i = 0; i <= K; ++ i) ans = min(ans, d[1][i]);return ans;
}int main()
{int t;scanf("%d", &t);while(t --){scanf("%d%d%d%d%d", &A, &B, &M, &L, &K);init();for(int i = 0; i < M; ++ i){int x, y, c;scanf("%d%d%d", &x, &y, &c);g[x][y] = g[y][x] = c;}floyd();printf("%d\n", spfa());}return 0;
}
这篇关于uva 10269 最短路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!