?
?
Paid Roads
| Time Limit: 1000MS |
? |
Memory Limit: 65536K |
| Total Submissions: 5383 |
? |
Accepted: 1923 |
?
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 ifrom 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.
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 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, Pi ≤ Ri (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
题意: 一共有编号从1~N的N个城市，城市之间有m条道路，一些路是要收费的。如果从ai到bi之前有经过ci城市，则收Pi的钱，否则收Ri的钱。求从城市1到城市N最小的花费。
题解: DFS~~ 搜索所有的路径，点可以重复走~~ 但是有个约束条件，一个点顶多走三次，不然就形成环出不来 了~~
PS: 开始题目意思没看懂....?.........
AC 代码:
#include
#define Max 9999999
using namespace std;
int map[11][5],n,m,count=0,res=Max;
int p[11],pt[11]={0};
void dfs(int k){
if(k==n){
if(count
>n>>m; for(int i=1;i<=m;i++) p[i]=1; for(int i=1;i<=m;i++) cin>>map[i][0]>>map[i][1]>>map[i][2]>>map[i][3]>>map[i][4]; dfs(1); if(res!=Max) cout<