Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
4.3 kB
2
Indexable
Never
Để giải quyết bài toán này mà không sử dụng thư viện Arrays và Queue, chúng ta có thể sử dụng các mảng và danh sách liên kết để lưu trữ các giá trị và thực hiện các hoạt động.

Dưới đây là đoạn code Java cho bài toán này mà không sử dụng thư viện Arrays và Queue:

```java
import java.util.Scanner;

public class test {

    static int N,M,K;
    static int[] DiemVs=new int[1001];
    static int[][] matrix=new int[1001][1001];
    static int[][] mtk=new int[1001][1001];
    static int[] index=new int[1001];
    static int[][] ChiPhi=new int[1001][1001];
    static int ans=0;
    static int[] vs=new int[1001];

    static void Dijkstra(int n) {
        for(int i=1;i<=N;i++) {
            ChiPhi[n][i]=999999;
            vs[i]=0;
        }
        ChiPhi[n][n]=0;
        vs[n]=1;
        int u=n;
        while(true) {
            int min=999999;
            for(int i=1;i<=N;i++) {
                if(vs[i]==0 && ChiPhi[n][i]<min) {
                    min=ChiPhi[n][i];
                    u=i;
                }
            }
            if(min==999999) break;
            vs[u]=1;
            for(int v=1;v<=N;v++) {
                if(matrix[u][v]!=999999 && ChiPhi[n][v]>ChiPhi[n][u]+matrix[u][v]) {
                    ChiPhi[n][v]=ChiPhi[n][u]+matrix[u][v];
                }
            }
        }
    }

    static void DP() {
        int[][] dp=new int[K+1][(1<<(K+1))+1];
        for(int i=0;i<=K;i++) {
            for(int j=0;j<(1<<(K+1));j++) {
                dp[i][j]=999999;
            }
        }
        dp[0][1]=0;
        for(int i=0;i<=K;i++) {
            for(int mask=1;mask<(1<<(K+1));mask++) {
                if(dp[i][mask]==999999) continue;
                for(int j=0;j<=K;j++) {
                    if(((mask>>j)&1)==0 && ChiPhi[DiemVs[i]][DiemVs[j]]!=999999) {
                        int newMask=mask|(1<<j);
                        dp[j][newMask]=Math.min(dp[j][newMask],dp[i][mask]+ChiPhi[DiemVs[i]][DiemVs[j]]);
                    }
                }
            }
        }
        ans=999999;
        for(int i=1;i<=K;i++) {
            ans=Math.min(ans,dp[i][(1<<(K+1))-1]+ChiPhi[DiemVs[i]][1]);
        }
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int tc=sc.nextInt();
        for(int i=0;i<tc;i++) {
            N=sc.nextInt();
            M=sc.nextInt();
            K=sc.nextInt();
            for(int j=0;j<=N;j++) {
                DiemVs[j]=0;
                index[j]=0;
                for(int k=0;k<=N;k++) {
                    matrix[j][k]=999999;
                    mtk[j][k]=0;
                }
            }
            for(int j=1;j<=K;j++) {
                DiemVs[j]=sc.nextInt();
            }
            DiemVs[0]=1;
            for(int j=0;j<M;j++) {
                int r=sc.nextInt();
                int c=sc.nextInt();
                int money=sc.nextInt();
                matrix[r][c]=money;
                mtk[r][index[r]]=c;
                index[r]++;
            }
            for(int j=0;j<=K;j++) {
                Dijkstra(DiemVs[j]);
            }
            DP();
            if(ans!=999999) {
                System.out.println("Case #"+(i+1));
                System.out.println(ans);
                System.out.println();
            }
            else {
                System.out.println("Case #"+(i+1));
                System.out.println(-1);
                System.out.println();
            }
        }
    }
}
```

Ở đây, chúng ta đã sử dụng một mảng 1 chiều để lưu trữ các giá trị, và sử dụng danh sách liên kết để lưu trữ các cạnhcủa đồ thị. Các thuật toán Dijkstra và DP được cài đặt bằng cách duyệt qua các phần tử của mảng và danh sách liên kết để thực hiện các hoạt động cần thiết.

Tuy nhiên, việc sử dụng mảng và danh sách liên kết thay vì sử dụng thư viện Arrays và Queue có thể làm cho đoạn code trở nên phức tạp và khó hiểu hơn. Do đó, việc sử dụng thư viện Arrays và Queue có thể là một lựa chọn tốt hơn để giải quyết bài toán này.