uva 10269 最短路

大家好，欢迎来到IT知识分享网。

求两次最短路

#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  #define MOD  #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; }