POJ 3411 Paid Roads(DFS)

POJ 3411 Paid Roads(DFS)

題意 你要從第1個城市到第N個城市去 有m條路 每條路用a, b, c, p, r 表示 你從第a個城市到第b個城市時 若之前經過或現在位於第c個城市 過路費就是p元 否則就是r元 求你到達第N個城市最少用多少過路費

由於最多只有10個城市 10條路 這個題就變得很簡單了 直接暴力dfs就行 可以用狀態壓縮來存儲已經走過了哪些城市 由於最多只有10條路 從某個城市出發要一條 回這個城市也要一條 所以一個城市最多經過5次 這個可以作為dfs的結束條件

 

#include 
#include 
#include 
using namespace std;

const int N = 11, INF = 2333333;
int n, m, ans, vis[N];
struct road{
    int a, b, c, p, r;
} rd[N];

//當前所在城市, 到過哪些城市, 當前已經用了多少過路費
void dfs(int p, int s, int v)
{
    if(vis[p] > 5) return;
    s = s | 1 << (p - 1);
    if(p == n)
    {
        ans = min(ans, v);
        return;
    }

    for(int i = 0; i < m; ++i)
    {
        if(rd[i].a != p) continue;
        ++vis[rd[i].b];
        if(s & 1 << (rd[i].c - 1)) //到過城市c
            dfs(rd[i].b, s, v + rd[i].p);
        else dfs(rd[i].b, s, v + rd[i].r);
        --vis[rd[i].b]; //回溯
    }
}

int main()
{
    while(~scanf(%d%d, &n, &m))
    {
        for(int i = 0; i < m; ++i)
            scanf(%d%d%d%d%d, &rd[i].a, &rd[i].b, &rd[i].c, &rd[i].p, &rd[i].r);

        ans = INF;
        memset(vis, 0, sizeof(vis));
        dfs(1, 0, 0);
        if(ans == INF) puts(impossible);
        else printf(%d
, ans);
    }

    return 0;
}

Paid Roads

Description

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 a_i to city b_i:

in advance, in a city c_i (which may or may not be the same as a_i);after the travel, in the city b_i.

The payment is P_i in the first case and R_i in the second case.

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

Input

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 a_i, b_i, c_i, P_i, R_i (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 ≤ P_i , R_i ≤ 100, P_i ≤ R_i (1 ≤ i ≤ m).

Output

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’.

Sample Input

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

Sample Output

110

Source

Northeastern Europe 2002, Western Subregion