46 lines
1.1 KiB
C++
46 lines
1.1 KiB
C++
|
#include<stdio.h>
|
||
|
|
#include<vector>
|
||
|
|
typedef struct{
|
||
|
|
int to;
|
||
|
|
int time;
|
||
|
|
int cost;
|
||
|
|
} path;
|
||
|
|
using namespace std;
|
||
|
|
int start,target;
|
||
|
|
int best_cost=2147483647;
|
||
|
|
int time_limit;
|
||
|
|
int m,n;
|
||
|
|
vector<path> graph[66000];
|
||
|
|
bool visited[66000]={0};
|
||
|
|
void dfs(short from,int time,int cost){
|
||
|
|
visited[from]=true;
|
||
|
|
for(auto i=graph[from].begin();i<graph[from].end();i++){
|
||
|
|
if(i->to==target){
|
||
|
|
if(time+i->time<=time_limit&&cost+i->cost<best_cost){
|
||
|
|
best_cost=cost+i->cost;
|
||
|
|
}
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
else if(time+i->time>time_limit||cost+i->cost>best_cost||visited[i->to]==true){
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
dfs(i->to,time+i->time,cost+i->cost);
|
||
|
|
}
|
||
|
|
visited[from]=false;
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
int main(){
|
||
|
|
int from,to,time,cost;
|
||
|
|
scanf("%d%d",&n,&m);
|
||
|
|
for(int i=0;i<m;i++){
|
||
|
|
scanf("%d%d%d%d",&from,&to,&time,&cost);
|
||
|
|
graph[from].push_back({to,time,cost});
|
||
|
|
}
|
||
|
|
scanf("%d%d%d",&start,&target,&time_limit);
|
||
|
|
dfs(start,0,0);
|
||
|
|
if(best_cost==2147483647){
|
||
|
|
best_cost=-1;
|
||
|
|
}
|
||
|
|
printf("%d",best_cost);
|
||
|
|
return 0;
|
||
|
|
}
|