Untitled
unknown
plain_text
2 years ago
9.5 kB
9
Indexable
<dd><p class="MsoNormal" align="center" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����; text-align: center;"><b>Tuần trăng mật<o:p></o:p></b></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">Đám cưới anh Uranus diễn ra rất vui vẻ, chỉ có Tomoky là có chút hậm hực. Sau đám cưới, anh Uranus muốn đi tuần trăng mật ở thành phố Đà Lạt xinh đẹp.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">Thành phố Đà Lạt gồm n điểm du lịch trọng điểm, được đánh số từ 1 tới n. Hệ thống giao thông trong vùng gồm m (m <= n*(n-1)) tuyến đường một chiều khác nhau, tuyến đường thứ j (j = 1,2,…m) cho phép đi từ địa điểm u_j tới địa điểm v_j với chi phí đi lại là số nguyên dương c(u_j, v_j).<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">Anh Uranus muốn xuất phát từ điểm du lịch 1 và đi thăm k địa điểm du lịch s_1, s_2, …, s_k (khác địa điểm 1) và sau đó quay về địa điểm xuất phát 1 với tổng chi phí là nhỏ nhất.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">Cho thông tin về hệ thống giao thông và k địa điểm du lịch s_1, s_2, …, s_k. Hãy giúp anh Uranus xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch 1 và đi thăm k địa điểm s_1, s_2, …, s_k sau đó quay về địa điểm du lịch 1 với tổng chi phí nhỏ nhất.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><b>Input<o:p></o:p></b></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">• Dòng đầu tiên chứa số nguyên dương T là số bộ test. Mỗi bộ test gồm:<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">• Dòng thứ nhất chứa 3 số nguyên n, m, k (n <= 1000 và k <= 15).<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">• Dòng thứ hai chứa k số nguyên dương s_1, s_2, …, s_k.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">• Dòng thứ j trong m dòng tiếp theo chứa 3 số nguyên dương u_j, v_j, c(u_j, v_j) cho biết thông tiên về tuyến đường thứ j. Biết rằng u_j luôn khác v_j, và c(u_j, v_j) <= 10^9.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><b>Output<o:p></o:p></b></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">In ra một số nguyên là tổng chi phí nhỏ nhất tìm được. Nếu không tìm được một hành trình du lịch nào, in ra số -1.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><b>Example<o:p></o:p></b></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><b>Input:<o:p></o:p></b></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">1<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">6 8 2<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">2 5<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">1 2 4<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">2 4 2<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">4 3 3<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">3 1 4<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">4 1 5<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">3 5 5<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">5 3 1<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">5 6 7</span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"> Output:</p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;">Case #1</p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;">19</p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><br></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;">Case #2</p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;">57</p></dd> package Buoi27.Tuan_trang_mat; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int nTourism; static int mLine; static int kAddress; static int[] address; static int[][] list; static int[] info; static long[][] expense = new long[1005][1005]; static long[][] matrix = new long[1005][1005]; static int[] queue = new int[1000 * 1000 * 2]; static int head; static int tail; static long[] visited; static int[] visited_BT; static int[] choose; static long min; static boolean flag; public static void enQueue(int value) { tail++; queue[tail] = value; } public static int deQueue() { head++; return queue[head]; } public static void input(Scanner sc) { nTourism = sc.nextInt(); mLine = sc.nextInt(); kAddress = sc.nextInt() + 1; address = new int[kAddress]; address[0] = 0; for (int i = 1; i < kAddress; i++) { address[i] = sc.nextInt() - 1; } list = new int[nTourism][mLine]; info = new int[nTourism]; for (int i = 0; i < mLine; i++) { int a = sc.nextInt() - 1; int b = sc.nextInt() - 1; expense[a][b] = sc.nextLong(); list[a][info[a]] = b; info[a]++; } } public static void BFS(int x) { head = tail = -1; visited = new long[nTourism]; visited[x] = 1; enQueue(x); int temp; while (head != tail) { temp = deQueue(); for (int i = 0; i < info[temp]; i++) { int a = list[temp][i]; if (visited[a] == 0 || visited[a] > visited[temp] + expense[temp][a]) { visited[a] = visited[temp] + expense[temp][a]; matrix[x][a] = visited[temp] + expense[temp][a] - 1; enQueue(a); } } } for (int i = 0; i < kAddress; i++) { if (matrix[x][address[i]] == 0 && x != address[i]) { flag = false; return; } } } public static void backtrack(int k, long sum) { if(sum>=min){ return; } if (k == kAddress) { sum += matrix[choose[k-1]][0]; if (min > sum) { min = sum; } return; } for (int i = 1; i < kAddress; i++) { if (visited_BT[i] == 0) { choose[k] = address[i]; visited_BT[i] = 1; backtrack(k + 1, sum + matrix[choose[k - 1]][choose[k]]); choose[k] = 0; visited_BT[i] = 0; } } } public static void solve() { for (int i = 0; i < kAddress; i++) { flag = true; BFS(address[i]); if (!flag) { System.out.println(-1); return; } } min = Long.MAX_VALUE; visited_BT = new int[kAddress]; visited_BT[0] = 1; choose = new int[kAddress]; choose[0] = 0; backtrack(1, 0); System.out.println(min); } public static void main(String[] args) throws FileNotFoundException { // TODO Auto-generated method stub long start = System.currentTimeMillis(); System.setIn(new FileInputStream( "C:\\Users\\SVMC\\Downloads\\input (1).txt")); // System.setIn(new FileInputStream("input.txt")); Scanner sc = new Scanner(System.in); int T; T = sc.nextInt(); for (int test_case = 1; test_case <= T; test_case++) { input(sc); System.out.println("Case #"+test_case); solve(); System.out.println(); } long end = System.currentTimeMillis(); System.out.println((double) (end - start) / 1000); } }
Editor is loading...