Untitled

#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);	
		}
	}
}