VDANGER SPOJ- Nguy hiểm rõ ràng trước mắt
Nông dân John đang ở trên một con thuyền nhỏ và đang tìm kiếm kho báu ở 1 trong số N (1 <= N <= 100) hòn đảo (đánh số từ 1..N) ở vùng biển Ca-ri-bò. Bản đồ kho báu cho John biết John cần phải thực hiện 1 hành trình đi qua đảo A_1, A_2, … A_M (2 <= M <= 10,000), ...
Nông dân John đang ở trên một con thuyền nhỏ và đang tìm kiếm kho báu ở 1 trong số N (1 <= N <= 100) hòn đảo (đánh số từ 1..N) ở vùng biển Ca-ri-bò.
Bản đồ kho báu cho John biết John cần phải thực hiện 1 hành trình đi qua đảo A_1, A_2, … A_M (2 <= M <= 10,000), bắt đầu từ đảo 1 và kết thúc ở đảo N trước khi kho báu biến mất. Anh ta có thể đến thăm các đảo khác và thăm bao nhiêu lần tùy thích, miễn là hành trình của ông ta phải chứa dãy A_1,..A_M là 1 dãy con (không nhất thiết phải liên tiếp nhau).
John muốn tránh đụng độ cướp biển và biết được mức-độ-bị-cướp (0 <= mức-độ-bị-cướp <= 100,000) khi đi lại giữa 2 hòn đảo với nhau. Độ nguy hiểm của hành trình của John sẽ là tổng các mức-độ-bị-cướp trên các tuyến đường mà John đi qua.
Hãy giúp John tìm được 1 hành trình ít nguy hiểm nhất để có thể lấy được kho báu.
Dữ liệu
- Dòng 1: 2 số nguyên cách nhau bởi dấu cách: N và M
- Dòng 2..M+1: Dòng i+1 mô tả chứa 1 số nguyên là đảo thứ i mà John cần phải tới: A_i
- Dòng M+2..N+M+1: Dòng i+M+1 chứa N số nguyên cách nhau bởi dấu cách tương ứng là mức-độ-bị-cướp trên tuyến đường đi giữa đảo i và đảo 1, 2,…N; đảm bảo số nguyên thứ i luôn là số 0.
Kết quả
- Dòng 1: Độ nguy hiểm nhỏ nhất của hành trình của John.
Ví dụ
Dữ liệu
3 4
1
2
1
3
0 5 1
5 0 2
1 2 0
Kết quả
7
Giải thích:
Hành trình có độ nguy hiểm nhỏ nhất là 7. John sẽ đi như sau:
1, 3, 2, 3, 1, and 3. Yêu cầu của bản đồ là phải chứa dãy
(1, 2, 1, và 3) và hành trình này thỏa mãn yêu cầu. Chúng ta sẽ tránh đi
trên đường nối giữa 2 đảo 1 và 2 vì nó có mức-độ-bị-cướp.
Thuật toán:sử dụng dijkstra hoặc floyd để tìm đường đi ngắn nhất giữa các cặp đỉnh.kết quả của bài toán sẽ là tổng kc[1][x[1]]+kc[x[2]][x[3]]+…+kc[x[m]][n];
Code:
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 | //saker1417 #include <bits/stdc++.h> #define maxn 101 #define oo 1000000001 #define x first #define y second using namespace std; typedef pair < long long , int > LI; typedef pair < int , int > II; vector < II > g[maxn]; set < LI > q; int n,m,deg[maxn],cl[maxn],x[10001]; long long kc[maxn],kc1[maxn][maxn],d[maxn][maxn]; void doc() { cin>>n>>m; for(int i=1;i<=m;i++) cin>>x[i]; for(int u=1;u<=n;u++) for(int v=1;v<=n;v++) { int w; cin>>w; d[u][v]=w; deg[u]++; g[u].push_back(II(v,w)); } } void dij(int xp) { for(int i=1;i<=n;i++) cl[i]=0,kc[i]=oo; kc[xp]=0; cl[xp]=1; q.insert(LI(0,xp)); while(!q.empty()) { II t=*q.begin(); q.erase(t); int u=t.y; for(int i=0;i<deg[u];i++) { int v=g[u][i].x,l=g[u][i].y; if(cl[v]==0) { cl[v]=1; kc[v]=kc[u]+l; q.insert(LI(kc[v],v)); }else if(kc[v]>kc[u]+l) { q.erase(LI(kc[v],v)); kc[v]=kc[u]+l; q.insert(LI(kc[v],v)); } } } } void floyd() { for(int k=1;k<=n;k++) for(int u=1;u<=n;u++) for(int v=1;v<=n;v++) d[u][v]=min(d[u][k]+d[k][v],d[u][v]); long long kq=d[1][x[1]]+d[x[m]][n]; for(int i=1;i<=m-1;i++) kq+=d[x[i]][x[i+1]]; cout<<kq; } void tinh() { for(int i=1;i<=n;i++) { dij(i); for(int j=1;j<=n;j++) kc1[i][j]=kc[j]; } long long kq=kc1[1][x[1]]+kc1[x[m]][n]; for(int i=1;i<=m-1;i++) kq+=kc1[x[i]][x[i+1]]; cout<<kq; } int main() { freopen("VDANGER.inp","r",stdin); freopen("VDANGER.out","w",stdout); ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); doc(); tinh(); } |
