首页 > 专题系列 > Java解POJ > POJ 3411 Paid Roads [解题报告] Java
2013
11-12

POJ 3411 Paid Roads [解题报告] Java

Paid Roads

问题描述 :

A network of m roads connects N cities (numbered from 1 to N). There may be more than one road connecting one city with another. Some of the roads are paid. There are two ways to pay for travel on a paid road i from city ai to city bi:

  • in advance, in a city ci (which may or may not be the same as ai);
  • after the travel, in the city bi.

The payment is Pi in the first case and Ri in the second case.

Write a program to find a minimal-cost route from the city 1 to the city N.

输入:

The first line of the input contains the values of N and m. Each of the following m lines describes one road by specifying the values of ai, bi, ci, Pi, Ri (1 ≤ i m). Adjacent values on the same line are separated by one or more spaces. All values are integers, 1 ≤ m, N ≤ 10, 0 ≤ Pi , Ri ≤ 100, PiRi (1 ≤ i m).

输出:

The first and only line of the file must contain the minimal possible cost of a trip from the city 1 to the city N. If the trip is not possible for any reason, the line must contain the word ‘impossible’.

样例输入:

4 5
1 2 1 10 10
2 3 1 30 50
3 4 3 80 80
2 1 2 10 10
1 3 2 10 50

样例输出:

110

解题代码:

//* @author: 
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Node{
    int a, b, c, p, r;
}

public class Main{
    
    Node edge[] = new Node[11];
    int n, k, tot, ans;
    int use[] = new int[11];
    
    void dfs(int i, int money, int dp){
        if(edge[i].b == n){
            if(money< tot)tot = money;
            return;
        }
        for(int j = 1;j<=k;j++){
            if(edge[j]. a == edge[i].b && use[j]<=1){
                use[j]++;
                int min = edge[j].r;
                int b = 1<< (edge[j].b - 1);
                int c = 1<< (edge[j].c - 1);
                if((dp|c) == dp && edge[j].p < edge[j].r)
                    min = edge[j].p;
                dfs(j, money+min, (dp|b));
                use[j]--;
            }
        }
    }
    void solve() throws IOException{
       // BufferedReader cin = new BufferedReader(new FileReader(new File("in")));
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        int i, a, b;
        String read;
        read = cin.readLine();
        n = Integer.parseInt(read.split(" ")[0]);
        k = Integer.parseInt(read.split(" ")[1]);
        for(i=1;i<=k;i++){
            read = cin.readLine();
            if(edge[i] == null)edge[i] = new Node();
            edge[i].a = Integer.parseInt(read.split(" ")[0]);
            edge[i].b = Integer.parseInt(read.split(" ")[1]);
            edge[i].c = Integer.parseInt(read.split(" ")[2]);
            edge[i].p = Integer.parseInt(read.split(" ")[3]);
            edge[i].r = Integer.parseInt(read.split(" ")[4]);
        }
        if(n == 1){
            System.out.println("0");
            return;
        }
        ans = 1<< 29;
        for(i=1;i<=k;i++){
            tot = 1<< 29;
            if(edge[i].a == 1){
                use[i]++;
                b = 1<< (edge[i].b - 1);
                a = 1<< (edge[i].a - 1);
                dfs(i, edge[i].r, a|b);
                use[i]--;
            }
            if(tot< ans)ans = tot;
        }
        if(ans == 1<< 29)System.out.println("impossible");
        else System.out.println(ans);
        
    }
    
    public static void main(String[] args) throws IOException{
        Main test = new Main();
        test.solve();
    }
}

  1. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks