道路 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 102using 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;}
评论