Untitled
unknown
plain_text
2 years ago
5.7 kB
3
Indexable
#include <iostream> #define MAX_QUEUE 1000 #define LLONG_MAX 9223372036854775807 using namespace std; class Queue { int A[MAX_QUEUE]; int front, rear; public: Queue(); bool is_Empty(); bool is_Full(); void enQueue(int inValue); int deQueue(); int Qpeek(); void reset(); private: }; Queue::Queue() { front = rear = -1; } bool Queue::is_Empty(){ if(front == rear) return true; return false; } bool Queue::is_Full(){ if(rear == MAX_QUEUE - 1) return true; return false; } void Queue::enQueue(int inValue){ A[++rear] = inValue; } int Queue::deQueue(){ front++; return A[front]; } int Queue::Qpeek(){ return A[front+1]; } void Queue::reset(){ front = rear = -1; } int T, m,n,k; int Map[1000][1000]; long long records[1000]; int Location[16]; long long LocationCost[16][16]; Queue mQueue; void BFS(int from){ mQueue.reset(); for (int i = 0; i < n; i++) { records[i] = LLONG_MAX; } records[from] = 0; mQueue.enQueue(from); while (mQueue.is_Empty() == false) { int temp = mQueue.deQueue(); for (int i = 0; i < n; i++) { if( temp != i && Map[temp][i] != -1 && Map[temp][i] + records[temp] < records[i] ){ records[i] = Map[temp][i] + records[temp]; mQueue.enQueue(i); } } } } long long historycost[16]; long long min_cost = LLONG_MAX; bool check_all(){ for (int i = 1; i <= k; i++) { if(historycost[i] == LLONG_MAX){ return false; } } return true; } long long dp[1 << 15][16]; int main(){ cin >> T; Location[0] = 0; for (int tc = 0; tc < T; tc++) { cin >> n >> m >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Map[i][j] = -1; } } for (int i = 1; i <= k; i++) { cin >> Location[i]; Location[i] = Location[i] - 1; } int from, to, cost; for (int i = 0; i < m; i++) { cin >> from >> to >> cost; Map[from-1][to-1] = cost; } for (int i = 0; i <= k; i++) { BFS(Location[i]); for (int j = 0; j <= k; j++) { LocationCost[i][j] = records[Location[j]]; } } for (int i = 0; i < k; i++) { for (int j = 0; j < 1 << k; j++) { dp[j][i] = LLONG_MAX; } } for (int i = 0; i < k; i++) { dp[1 << i][i] = LocationCost[0][i+1]; } for (int mask = 1; mask < (1 << k); mask++) { for (int i = 0; i < k ; i++) { if (((mask >> i) & 1) == 0) continue; for (int j = 0; j < k; j++) { if ((mask >> j) & 1) continue; dp[mask | (1 << j)][j] = dp[mask | (1 << j)][j] > dp[mask][i] + LocationCost[i+1][j+1] ? dp[mask][i] + LocationCost[i+1][j+1] : dp[mask | (1 << j)][j]; } } } long long res = LLONG_MAX; for (int i = 0; i < k; i++) { if(LocationCost[i+1][0] != LLONG_MAX) res = dp[(1<<k) - 1][i] + LocationCost[i+1][0] < res ? dp[(1<<k) - 1][i] + LocationCost[i+1][0] : res; } if(res != LLONG_MAX) cout << "Case #" << tc + 1 << endl << res << endl << endl; else { cout << "Case #" << tc + 1 << endl << -1 << endl << endl; } } return 0; } java import java.util.Scanner; public class Solution { static int T,n,tuyenDuong,diaDiemCanDiQua,valueX,valueY,res; static int[][] a = new int[1001][1001]; static int[] visited = new int[1001]; static int[] dxDiaDiemCanQua = new int[1001]; static int[] visited2 = new int[1001]; private static Scanner scanner; static int idx; public static void resetMaTran(){ for (int i = 1; i <=n ; i++) { for (int j = 1; j <=n; j++) { a[i][j]=0; } } } public static void resetVisited(){ for (int i = 1; i <=n ; i++) { visited[i]=0; } } public static void resetDiaDiemCanQua(){ for (int i = 0; i <1001; i++) { visited2[i]=0; } } public static void bt(int index, int sum,int count){ // dieu kien dung if (count==diaDiemCanDiQua) { if (sum<res) { idx=index; res=sum; } } if (sum>res) { return; } // xu ly for (int i = 1; i <=n ; i++) { if (visited[i]==0&&a[index][i]!=0) { visited[i]=1; if (visited2[i]==1) { bt(i, sum+a[index][i], count+1); }else{ bt(i, sum+a[index][i], count); } visited[i]=0; } } } public static void bt(int index, int sum){ // dieu kien dung if (index==1) { if (sum<res) { res=sum; } } if (sum>res) { return; } // xu ly for (int i = 1; i <=n ; i++) { if (visited[i]==0&&a[index][i]!=0) { visited[i]=1; if (visited2[i]==1) { bt(i, sum+a[index][i]); }else{ bt(i, sum+a[index][i]); } visited[i]=0; } } } public static void main(String[] args){ //System.setIn(new FileInputStream("src/input.txt")); Scanner scanner = new Scanner(System.in); T =scanner.nextInt(); for (int tc = 1; tc <= T ; tc++) { n =scanner.nextInt(); tuyenDuong =scanner.nextInt(); diaDiemCanDiQua =scanner.nextInt(); resetMaTran(); resetVisited(); resetDiaDiemCanQua(); for (int i = 0; i < diaDiemCanDiQua; i++) { dxDiaDiemCanQua[i]=scanner.nextInt(); visited2[dxDiaDiemCanQua[i]]=1; } for (int i = 1; i <=tuyenDuong ; i++) { valueX =scanner.nextInt(); valueY = scanner.nextInt(); a[valueX][valueY] =scanner.nextInt(); } // xu ly res=999; idx=0; visited[1]=1; bt(1,0,0); int res1=res; res=999; resetVisited(); bt(idx,0); int res2=res; System.out.println("Case #"+tc); System.out.println(res1+res2); } } }
Editor is loading...