A40946. 道路
填空题
困难
知识点
题目描述
道路
题目描述
N个以 1 … N 标号的城市通过单向的道路相连:。每条道路包含两个参数：道路的长度和需要为该路付的通行费（以金币的数目来表示）
Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后，Bob和她分手了，并且决定搬到城市N。他希望能够尽可能快的到那，但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径，前提是他能够付的起通行费。
输入
第一行包含一个整数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
参考答案
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
struct Road
{
int d,L,t;
};
int N,K,R;
vector < vector <Road> > 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<len;i++)//枚举和s相邻接额情况
{
Road r=G[s][i];
if(!visited[r.d])//如果没有被走过
{
/*下面三个if语句是三条剪枝条件*/
if(totalCost+r.t>K)//如果当前花销大于K了
continue;
if(totalLen+r.L>=minLen)//如果当前的路径已经超过了已存在的最短路径，那就没必要往后dfs了
continue;
//如果存在两种方式都到达同一点并且花销相同，但是如果当前的长度大于另一种方式的长度，则continue
if(totalLen+r.L>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>>K>>N>>R;
for(int i=0;i<R;i++)
{
int s;
Road r;
cin>>s;
cin>>r.d>>r.L>>r.t;
G[s].push_back(r);
}
totalCost=0;
totalLen=0;
minLen=1<<30;//无穷大
memset(visited,0,sizeof(visited));
for(int i=1;i<=N;i++)
for(int j=0;j<10010;j++)
minL[i][j]=1<<30;
visited[1]=1;
Dfs(1);
if(minLen<(1<<30))
cout<<minLen<<endl;
else
cout<<-1<<endl;
return 0;
}
上一题
下一题