主要时floyd判断出利用飞鞋生成的DIS 。其他SPFA或DIJKSTRA都可以
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} #define MAXN 110 const int INF = 0x3f3f3f3f ; int dis[MAXN][MAXN]; int A,B,M,L,K; int dp[MAXN][MAXN]; bool inq[MAXN][MAXN]; struct node { int idx; int cnt; }; void read() { scanf("%d%d%d%d%d",&A,&B,&M,&L,&K); memset(dis,0x3f,sizeof(dp)); for (int i = 0; i <= A + B; i++) dis[i][i] = 0; while (M--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); dis[u][v] = dis[v][u] = w; } for (int k = 1; k <= A; k++) for (int i = 1; i <= A + B; i++) for (int j = 1; j <= A + B; j++) dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]); } void SPFA() { memset(inq,false,sizeof(inq)); memset(dp,0x3f,sizeof(dp)); queue<node>q; while (!q.empty()) q.pop(); node tmp; tmp.cnt = K; tmp.idx = A + B; inq[A + B][K] = true; dp[A + B][K] = 0; q.push(tmp); while (!q.empty()) { node tmp = q.front(); q.pop(); int u = tmp.idx , num = tmp.cnt; inq[u][num] = false; //printf("%d %d ",u,num); for (int i = 1; i <= A + B; i++) { if (i == u) continue; if (dis[u][i] != INF) { // printf("dis[%d][%d] = %d ",u,i,dis[u][i]); // printf("%d ",dp[i][num - 1]); if (num > 0 && dis[u][i] <= L && dp[i][num - 1] > dp[u][num]) { dp[i][num - 1] = dp[u][num]; if (!inq[i][num - 1]) { inq[i][num - 1] = true; node temp; temp.idx = i; temp.cnt = num - 1; q.push(temp); } } if (dp[i][num] > dp[u][num] + dis[u][i]) { dp[i][num] = dp[u][num] + dis[u][i]; if (!inq[i][num]) { inq[i][num] = true; node temp; temp.idx = i; temp.cnt = num; q.push(temp); } } } } } int ans = INT_MAX; for (int i = 0; i <= K; i++) ans = min(ans,dp[1][i]); printf("%d ",ans); } int main() { // freopen("sample.txt","r",stdin); int T; scanf("%d",&T); while (T--) { read(); SPFA(); } return 0; }