fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. import static java.lang.Math.max;
  5. import static java.lang.Math.min;
  6. import static java.lang.Math.abs;
  7.  
  8. public class Main {
  9.     public static int mod = (int) 1e9 + 7;
  10.  
  11.     static class FastReader {
  12.         BufferedReader br;
  13.         StringTokenizer st;
  14.  
  15.         public FastReader() {
  16.             br = new BufferedReader(new InputStreamReader(System.in));
  17.         }
  18.  
  19.         String next() {
  20.             while (st == null || !st.hasMoreTokens()) {
  21.                 try {
  22.                     st = new StringTokenizer(br.readLine());
  23.                 } catch (IOException e) {
  24.                     e.printStackTrace();
  25.                 }
  26.             }
  27.             return st.nextToken();
  28.         }
  29.  
  30.         int nextInt() {
  31.             return Integer.parseInt(next());
  32.         }
  33.  
  34.         long nextLong() {
  35.             return Long.parseLong(next());
  36.         }
  37.  
  38.         double nextDouble() {
  39.             return Double.parseDouble(next());
  40.         }
  41.  
  42.         String nextLine() {
  43.             String str = "";
  44.             try {
  45.                 str = br.readLine().trim();
  46.             } catch (Exception e) {
  47.                 e.printStackTrace();
  48.             }
  49.             return str;
  50.         }
  51.     }
  52.  
  53.     static class FastWriter {
  54.         private final BufferedWriter bw;
  55.  
  56.         public FastWriter() {
  57.             this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
  58.         }
  59.  
  60.         public void print(Object object) throws IOException {
  61.             bw.append("" + object);
  62.         }
  63.  
  64.         public void println(Object object) throws IOException {
  65.             print(object);
  66.             bw.append("\n");
  67.         }
  68.  
  69.         public void println() throws IOException {
  70.             bw.append("\n");
  71.         }
  72.  
  73.         public void close() throws IOException {
  74.             bw.close();
  75.         }
  76.  
  77.         public void printLongArr(long[] arr) throws IOException {
  78.             for (long ele : arr) {
  79.                 print(ele + " ");
  80.             }
  81.             println();
  82.         }
  83.  
  84.         public void printIntArr(int[] arr) throws IOException {
  85.             for (int ele : arr) {
  86.                 print(ele + " ");
  87.             }
  88.             println();
  89.         }
  90.     }
  91.  
  92.     public static void main
  93.             (String[] args) {
  94.         try {
  95.             FastReader fin = new FastReader();
  96.             FastWriter fout = new FastWriter();
  97.  
  98.             int t = fin.nextInt();
  99.             while (t-- > 0) {
  100.                 int n = fin.nextInt();
  101.                 int m = fin.nextInt();
  102.                 int b = fin.nextInt();
  103.                 List<int[]> parcels = new ArrayList<>();
  104.                 int[][] edges = new int[m][3];
  105.                 for (int i = 0; i < m; i++) {
  106.                     edges[i][0] = fin.nextInt();
  107.                     edges[i][1] = fin.nextInt();
  108.                     edges[i][2] = fin.nextInt();
  109.                 }
  110.                 int z = fin.nextInt();
  111.                 int[][] requests = new int[z][3];
  112.                 for (int i = 0; i < z; i++) {
  113.                     int u = fin.nextInt();
  114.                     int v = fin.nextInt();
  115.                     int count = fin.nextInt();
  116.                     for (int k = 0; k < count; k++) {
  117.                     parcels.add(new int[]{u, v});
  118.                 }
  119.                 }
  120.                 int p = parcels.size();
  121.                 int[][] allSourceShortestMap = getAllPairShortestPath(edges, n);
  122.                 long dp[][] = new long[n + 1][1 << p];
  123.                 for(long dp1[] : dp){
  124.                     Arrays.fill(dp1,-1);
  125.                 }
  126.                 fout.println(recusiveHelper(b, 0, dp, allSourceShortestMap, parcels, b));
  127.  
  128.             }
  129.  
  130.             fout.close();
  131.         } catch (Exception e) {
  132.             e.printStackTrace();
  133.             return;
  134.         }
  135.     }
  136.  
  137.     // dp[i][mask] -> minimum cost to deliver packages represented by mask when courier is at location i
  138.     private static long recusiveHelper(int i, int mask, long[][] dp, int[][] allSourceShortestMap, List<int[]> parcels, int b) {
  139.         if (mask == (1 << parcels.size()) - 1) {
  140.             return allSourceShortestMap[i][b];
  141.         }
  142.         if (dp[i][mask] != -1) {
  143.             return dp[i][mask];
  144.         }
  145.         long minCost = Long.MAX_VALUE;
  146.         for (int j = 0; j < parcels.size(); j++) {
  147.             if ((mask & (1 << j)) == 0) {
  148.                 // taking the request
  149.                 int src = parcels.get(j)[0];
  150.                 int dest = parcels.get(j)[1];
  151.                 int travelCost = allSourceShortestMap[i][src] + allSourceShortestMap[src][dest];
  152.                 long costTaking = travelCost + recusiveHelper(dest, mask | (1 << j), dp, allSourceShortestMap, parcels, b);
  153.                 minCost = Math.min(minCost, costTaking);
  154.             }
  155.         }
  156.         return dp[i][mask] = minCost;
  157.     }
  158.  
  159.     private static int[][] getAllPairShortestPath(int[][] edges, int n) {
  160.         int[][] allSourceShortestPath = new int[n + 1][n + 1];
  161.         for (int i =1; i <= n; i++) {
  162.             allSourceShortestPath[i] = bellmanFord(i ,edges, n);
  163.         }
  164.         return allSourceShortestPath;
  165.     }
  166.  
  167.     private static int[] bellmanFord(int src, int[][] edges, int n) {
  168.         int dist[] = new int[n + 1];
  169.         Arrays.fill(dist, (int) 1e9);
  170.         dist[src] = 0;
  171.         for (int i = 1; i < n; i++) { // relaxing n-1 times
  172.             for (int[] edge : edges) {
  173.                 int u = edge[0];
  174.                 int v = edge[1];
  175.                 int edgeWeight = edge[2];
  176.                 if (dist[u] + edgeWeight < dist[v]) {
  177.                     dist[v] = dist[u] + edgeWeight;
  178.                 }
  179.                 // as road are  bidirectional so
  180.                 if (dist[v] + edgeWeight < dist[u]) {
  181.                     dist[u] = dist[v] + edgeWeight;
  182.                 }
  183.             }
  184.         }
  185.         return dist;
  186.     }
  187. }
  188.  
Success #stdin #stdout 0.12s 57420KB
comments (?)
stdin
copy 
1
5 7 2
1 2 7
1 3 5
1 5 2
2 4 10
2 5 1
3 4 3
3 5 4
3
1 4 2
5 3 1
5 1 1
stdout
copy 
43
https://ideone.com/1Kzx6O
problem COURIER, based on SPOJ submission 35419974 (JAVA), 2025-12-28 06:01:40
language:
Java (HotSpot 12)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!