2013
11-12

# POJ 3411 Paid Roads [解题报告] Java

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.File;
import java.io.FileNotFoundException;
import java.io.IOException;

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{
int i, a, b;
for(i=1;i<=k;i++){
if(edge[i] == null)edge[i] = new Node();
}
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. 希望可以去查查资料 其他地方不清楚 上海图书馆和天津图书馆都有 1960年 中国的人口较1959年”负增长”一千万左右 人口出生率和死亡率都出现大幅波动 具体数字记不清楚了 在没有大动乱和战争的情况下 中国的人口竟然减少 这本身也许可

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