首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#7466

道路(2024.3八级) N个以 1 ... N 标号的城市通过单向的道路相连:。每条道路包含两个参数:道路的长度和需要为该路付的通行费(以金币的数目来表示)…

道路(2024.3八级)

N个以 1 ... N 标号的城市通过单向的道路相连:。每条道路包含两个参数:道路的长度和需要为该路付的通行费(以金币的数目来表示)

Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后,Bob和她分手了,并且决定搬到城市N。他希望能够尽可能快的到那,但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径,前提是他能够付的起通行费。

时间限制:1000

内存限制:65536

输入

第一行包含一个整数K, 0 <= K <= 10000, 代表Bob能够在他路上花费的最大的金币数。第二行包含整数N, 2 <= N <= 100, 指城市的数目。第三行包含整数R, 1 <= R <= 10000, 指路的数目. 接下来的R行,每行具体指定几个整数S, D, L 和 T来说明关于道路的一些情况,这些整数之间通过空格间隔: S is 道路起始城市, 1 <= S <= N D is 道路终点城市, 1 <= D <= N L is 道路长度, 1 <= L <= 100 T is 通行费 (以金币数量形式度量), 0 <= T <=100 注意不同的道路可能有相同的起点和终点。

输出

输入结果应该只包括一行,即从城市1到城市N所需要的最小的路径长度(花费不能超过K个金币)。如果这样的路径不存在,结果应该输出-1。


样例输入

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

样例输出

11
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;algorithm&gt; #include&lt;cmath&gt; #include&lt;cstdio&gt; #include&lt;vector&gt; #include&lt;cstring&gt; using namespace std; struct Road {     int d,L,t; }; int N,K,R; vector &lt; vector &lt;Road&gt; &gt; G(110);//用二维数组表示临界表,G[s]表示和s邻接的路 int minLen;//全局变量,记录最短的路径长度 int totalCost;//当前状态的花费 int totalLen;//当前状态的长度 int visited[110]; int minL[110][10010];//minL[i][j]的意义是当到达i点是花费为j时的最短路径 void Dfs(int s) {     if(s==N)     {         minLen=min(minLen,totalLen);         return ;     }     int len=G[s].size();     for(int i=0;i&lt;len;i++)//枚举和s相邻接额情况     {         Road r=G[s][i];         if(!visited[r.d])//如果没有被走过         {             /*下面三个if语句是三条剪枝条件*/             if(totalCost+r.t&gt;K)//如果当前花销大于K了                 continue;             if(totalLen+r.L&gt;=minLen)//如果当前的路径已经超过了已存在的最短路径,那就没必要往后dfs了                 continue;             //如果存在两种方式都到达同一点并且花销相同,但是如果当前的长度大于另一种方式的长度,则continue             if(totalLen+r.L&gt;minL[r.d][totalCost+r.t])                 continue;             minL[r.d][totalCost+r.t]=totalLen+r.L;             visited[r.d]=1;             totalCost+=r.t;             totalLen+=r.L;             Dfs(r.d);             visited[r.d]=0;//因为可能存在多种方式的dfs的路径,所以每次dfs之后都要还原到之前的状态             totalCost-=r.t;             totalLen-=r.L;         }     } } int main() {     cin&gt;&gt;K&gt;&gt;N&gt;&gt;R;     for(int i=0;i&lt;R;i++)     {         int s;         Road r;         cin&gt;&gt;s;         cin&gt;&gt;r.d&gt;&gt;r.L&gt;&gt;r.t;         G[s].push_back(r);     }     totalCost=0;     totalLen=0;     minLen=1&lt;&lt;30;//无穷大     memset(visited,0,sizeof(visited));     for(int i=1;i&lt;=N;i++)         for(int j=0;j&lt;10010;j++)             minL[i][j]=1&lt;&lt;30;     visited[1]=1;     Dfs(1);     if(minLen&lt;(1&lt;&lt;30))         cout&lt;&lt;minLen&lt;&lt;endl;     else         cout&lt;&lt;-1&lt;&lt;endl;     return 0; }</pre>
这道题暂未补解析。