| 道路 |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Total submit users: 23, Accepted users: 13 |
| Problem 10183 : No special judgement |
| Problem description |
| 编号为1…N 的N个城市之间以单向路连接，每一条道路有两个参数： 路的长度和通过这条路需付的费用。 Bob和Alice生活在城市1，但是当Bob发现了Alice玩扑克时欺骗他之后，他决定与她翻脸，离开城市1前往城市N. Bob想尽快到达城市N，他是他的钱不多。我们希望你帮助Bob找到一条从城市1到城市N的总费用不超过Bob的承受能力的最短路径。 |
| Input |
| 输入的第1行包含一个整数K, 0 <= K <= 10000, 表示Bob能承受的最大费用；第2行包含一个整数N, 2 <= N <= 100,表示城市的总数；第3行包含整数R, 1 <= R <= 10000,表示道路的条数；接下来的R行，每行用S D L T（以空格隔开）表示一条道路： S：表示道路的出发城市，1 <= S <= N D：表示道路的目标城市，1 <= D <= N L：表示道路的长度，1 <= L <= 100 T：表示通过这条道路需付的费用，0 <= T <=100 |
| Output |
| 仅有的一行中输出总费用小余或等于最大费用K的最短路径的长度。如果这样的路径不存在，则仅仅输出 -1 。 |
| 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 |
| Problem Source |
| CSU 1st Contest |
//// 狂WA了几次, 原来两城市间可能不止两条道路, 好晕, 第一次用 C++ 写
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#define MAX_CITY 102
using namespace std;
class LOAD{
public:
int nLength,nTeil;
LOAD(int a=0, int b=0):nLength(a),nTeil(b){}
};
class CITY{
public:
vector<LOAD> vtLoad;
};
class STACK{
public:
int t,teil,length;
bool *pbPath;
STACK(int nt=0,int nteil=0,int nlength=0,bool *pB=NULL):
t(nt),teil(nteil),length(nlength),pbPath(pB){}
};
CITY gCity[MAX_CITY][MAX_CITY];
int main(){
int K,N,R,S,D,L,T,i;
cin>>K>>N>>R;
STACK s;
for(i=0; i<R; i++){
cin>>S>>D>>L>>T;
gCity[S][D].vtLoad.push_back(LOAD(L,T));
}
stack<STACK> stk;
list<bool*> plstMem;
bool* pB;
for(i=2; i<=N; i++){
for(int j=0; j<gCity[1][i].vtLoad.size(); j++){
pB = new bool[MAX_CITY];
plstMem.push_back(pB);
memset(pB,false,sizeof(bool)*MAX_CITY);
pB[1] = true;
stk.push( STACK(i,gCity[1][i].vtLoad[j].nTeil,
gCity[1][i].vtLoad[j].nLength,pB) );
}
}
int teil,length,from,min;
for(min=INT_MAX; !stk.empty();){
length = stk.top().length;
teil = stk.top().teil;
from = stk.top().t;
pB = stk.top().pbPath;
pB[from] = true;
stk.pop();
if(from==N){
min = min > length ? length : min;
continue;
}
for(i=1; i<=N; i++){
if(!pB[i]){
for(int j=0; j<gCity[from][i].vtLoad.size(); j++){
if(teil+gCity[from][i].vtLoad[j].nTeil<=K &&
length+gCity[from][i].vtLoad[j].nLength<min){
bool *p = new bool[MAX_CITY];
memcpy(p,pB,sizeof(bool)*MAX_CITY);
plstMem.push_back(p);
stk.push(STACK(i,teil+gCity[from][i].vtLoad[j].nTeil,
length+gCity[from][i].vtLoad[j].nLength,p));
}
}
}
}
}
list<bool*>::iterator f,it;
f = it =plstMem.begin();
for(it++; it!=plstMem.end(); it++){
delete[] (*f); f = it;
}
if(min==INT_MAX)
cout<<"-1";
else
cout<<min;
return 0;
}
评论