This can be done two ways using floyed-warshall algorithm and also using bfs;
Floyed warshall:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include <iostream> #include <queue> #include <cstring> #define INF 1500000 using namespace std; int gr[105][105]; int A,B,M,L,K; bool trace[105][15]; int d[105][15]; int shortestpath() { d[A+B][0]=0; queue<int> q; q.push(A+B); q.push(0); //trace[A+B][0]=1; while(!q.empty()) { int a = q.front();q.pop(); int boot = q.front();q.pop(); trace[a][boot]=0; for(int i=1;i<=A+B;i++) { if(i==a) continue; if(boot<K && gr[a][i]<=L) { if(d[i][boot+1]>d[a][boot]) { d[i][boot+1] = d[a][boot]; if(!trace[i][boot+1]) { trace[i][boot+1] = 1; q.push(i);q.push(boot+1); } } } if(d[i][boot]>d[a][boot]+gr[a][i]) { d[i][boot] = d[a][boot]+gr[a][i]; if(!trace[i][boot]) { trace[i][boot]=1; q.push(i);q.push(boot); } } } } int MN = INF; for(int i=0;i<=K;i++) { if(MN>d[1][i]) MN = d[1][i]; } cout<<MN<<"\n"; } int main() { int t; int x,y,z; cin>>t; while(t--) { cin>>A>>B>>M>>L>>K; for(int i=0;i<105;i++) for(int j=0;j<105;j++) { if(j<15) { d[i][j]=INF; trace[i][j] = false; } if(i==j) gr[i][j] = 0; else gr[i][j] = INF; } //cout<<gr[2][4]<<"\n"; while(M--) { cin>>x>>y>>z; gr[x][y] = z; gr[y][x] = z; } for(int k=1;k<=A;k++) { for(int i=1;i<=A+B;i++) { for(int j=1;j<=A+B;j++) { if(gr[i][k]==INF || gr[k][j]==INF) continue; if(gr[i][j]>gr[i][k]+gr[k][j]) gr[i][j] = gr[i][k]+gr[k][j]; } } } shortestpath(); } return 0; } |
BFS:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include <iostream> #include <queue> #include <cstring> using namespace std; int state[105][505][15];//state position,distance can cross by boot(L-cost),no of boot use left int A,B,M,L,K; int cost[105][105]; int main() { int t; int x,y,z; cin>>t; while(t--) { cin>>A>>B>>M>>L>>K; memset(cost,-1,sizeof(cost)); memset(state,63,sizeof(state)); int INF = state[0][0][0]; while(M--) { cin>>x>>y>>z; cost[x][y]=z; cost[y][x]=z; } state[A+B][0][K]=0; queue<int> q; q.push(A+B);q.push(0);q.push(K); while(!q.empty()) { int a = q.front();q.pop(); int l = q.front();q.pop(); int k = q.front();q.pop(); int par_cost = state[a][l][k]; for(int i=1;i<=A+B;i++) { if(cost[a][i]==-1) continue; int d = cost[a][i]; if(a<=A) { if(l>=d) { int ll = l-d; int aa = i; int kk = k; if(state[aa][ll][kk]> par_cost) { state[aa][ll][kk] = par_cost; q.push(aa);q.push(ll);q.push(kk); } } } if(k>0 && L>=d) { int ll = L-d; int aa = i; int kk = k-1; if(state[aa][ll][kk]>par_cost) { state[aa][ll][kk] = par_cost; q.push(aa);q.push(ll);q.push(kk); } } if(state[i][0][k]>(par_cost+d)) { state[i][0][k] = (par_cost+d); q.push(i);q.push(0);q.push(k); } } } int MN = INF; for(int i=0;i<=L;i++) { for(int j=0;j<=K;j++) { if(state[1][i][j]<MN) MN = state[1][i][j]; } } cout<<MN<<"\n"; } return 0; } |