/*
dfs比较好想，就是测试数据的问题，导致在遍历边的时候要倒着遍历才过！
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define Max 0x3f3f3f3f
using namespace std;
struct node{
int D;
int L, T;
node(int D, int L, int T){
this->D=D;
this->L=L;
this->T=T;
}
node(){
}
};
node v[105][1000];
int cnt[105];
int vis[105];
int maxCost, R, N, S, D, L, T;
int cost, dist;
void dfs(int cur, int d, int c){
int i;
if(cur == N){
if(dist>d){
dist=d;
if(cost>c) cost=c;
}
return ;
}
for(i=cnt[cur]-1; i>=0; --i)
if(!vis[v[cur][i].D] && c+v[cur][i].T<=maxCost && d+v[cur][i].L<dist){
vis[v[cur][i].D]=1;
dfs(v[cur][i].D, d+v[cur][i].L, c+v[cur][i].T);
vis[v[cur][i].D]=0;
}
}
int main(){
while(scanf("%d", &maxCost)!=EOF){
scanf("%d%d", &N, &R);
memset(cnt, 0, sizeof(cnt));
while(R--){
scanf("%d%d%d%d", &S, &D, &L, &T);
v[S][cnt[S]++]=node(D, L, T);
}
cost=dist=Max;
memset(vis, 0, sizeof(vis));
dfs(1, 0, 0);
if(cost<=maxCost)
printf("%d\n", dist);
else printf("-1\n");
}
return 0;
}
/*
spfa + 01背包
dist[next][j]=min(dist[cur][j-v[cur][i].T]+v[cur][i].L) j={v[cur][i].T。。。maxCost}
一维数组表示的是城市节点，二维表示的当前费用
dist[i][j]表示经过i城市，费用为j时总的路径长度！
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define Max 0x3f3f3f3f
using namespace std;
struct node{
int D;
int L, T;
node(int D, int L, int T){
this->D=D;
this->L=L;
this->T=T;
}
node(){
}
};
node v[105][1000];
int cnt[105];
int dist[105][10005];
int vis[105];
queue<int>q;
int maxCost, R, N, S, D, L, T;
int spfa(){
int i;
while(!q.empty()){
int cur = q.front();
q.pop();
vis[cur]=0;
for(i=0; i<cnt[cur]; ++i){
int next=v[cur][i].D;
for(int j=v[cur][i].T; j<=maxCost; ++j)
if(dist[next][j]>dist[cur][j-v[cur][i].T]+v[cur][i].L){
dist[next][j]=dist[cur][j-v[cur][i].T]+v[cur][i].L;
if(!vis[next]){
vis[next]=1;
q.push(next);
}
}
}
}
}
void bfs(int cur){
q.push(1);
memset(dist, 0x3f, sizeof(dist));
for(int i=0; i<105; ++i)
dist[1][i]=0;
vis[1]=1;
spfa();
}
int main(){
while(scanf("%d", &maxCost)!=EOF){
scanf("%d%d", &N, &R);
memset(cnt, 0, sizeof(cnt));
while(R--){
scanf("%d%d%d%d", &S, &D, &L, &T);
v[S][cnt[S]++]=node(D, L, T);
}
memset(vis, 0, sizeof(vis));
bfs(1);
int minDist=Max;
for(int i=1; i<=maxCost; ++i)
if(minDist>dist[N][i])
minDist=dist[N][i];
if(minDist!=Max)
printf("%d\n", minDist);
else printf("-1\n");
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3874165.html，如需转载请自行联系原作者
