购物网站建设 费用,网站制作潍坊,装潢设计与工艺教育专业,帮别人做钓鱼网站犯法吗题意#xff1a;
N个城市#xff0c;编号1到N。城市间有R条单向道路。有长度和过路费两个属性。Bob只有K块钱#xff0c;他想从城市1走到城市N。问最短共需要走多长的路。如果到不了N#xff0c;输出-1。
题目#xff1a;
N cities named with numbers 1 … N are conn…题意
N个城市编号1到N。城市间有R条单向道路。有长度和过路费两个属性。Bob只有K块钱他想从城市1走到城市N。问最短共需要走多长的路。如果到不了N输出-1。
题目
N cities named with numbers 1 … N are connected with one-way roads. Each road has two parameters associated with it : the road length and the toll that needs to be paid for the road (expressed in the number of coins). Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash.
We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.
Input
The first line of the input contains the integer K, 0 K 10000, maximum number of coins that Bob can spend on his way. The second line contains the integer N, 2 N 100, the total number of cities.
The third line contains the integer R, 1 R 10000, the total number of roads.
Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters : S is the source city, 1 S N D is the destination city, 1 D N L is the road length, 1 L 100 T is the toll (expressed in the number of coins), 0 T 100
Notice that different roads may have the same source and destination cities.
Output
The first and the only line of the output should contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins. If such path does not exist, only number -1 should be written to the output.
Sample Input
5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
Sample Output
11
分析
给了n个城市需要从城市1到城市n,求最短距离要是这样就是一道简单的最短路问题但题目有限制要求在满足花费即不超过k的情况下的最短路 1.首先考虑得用搜索迭代寻找在找到所有满足路径后选出最短的注意剪枝。 2.选用邻接表来存储无向图的时间空间复杂度是O(M)。 如果只是查询两个点之间是否相邻,邻接矩阵当然更快,但如果是做dfs的话,找当前节点相邻的点,如果用邻接矩阵的话每次都要从1扫到n,如果用邻接表遍历每个顶点的边
AC代码
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
typedef long long ll;
const int inf0x3f3f3f3f;
const int M1e410;
int n,m,k;
ll ans;
int a[M],b[M],c[M],d[M],fir[M],nex[M],book[M];
void dfs(int x/*当前到达城市*/,int y/*费用*/,int z/*路程*/)
{if(yn||zans)return ;if(xm){ansz;return ;}for(int ifir[x];i;inex[i])if(!book[i]){book[i]1;dfs(b[i],yd[i],zc[i]);book[i]0;}return ;
}
int main()
{scanf(%d%d%d,n,m,k);for(int i1;ik;i)/*care 变量要从1开始邻接表定义*/{scanf(%d%d%d%d,a[i],b[i],c[i],d[i]);nex[i]fir[a[i]];fir[a[i]]i;}ansinf;dfs(1,0,0);if(ansinf) printf(-1\n);else printf(%lld\n,ans);return 0;
}
