Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 1e5 + 10;
- const int INF = (1 << 30);
- typedef long long ll;
- const ll inf = (1LL << 59LL);
- struct node{
- int till, euro, time;
- node (){}
- node(int _t, int _timee, int _e){
- till = _t;
- time = _timee;
- euro = _e;
- }
- };
- vector<node> graph[5005];
- int n, m, S;
- bool visited[3005][6005];
- int idx[3005];
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin >> S >> n >> m;
- for(int i = 0; i < m; i++){
- int a, b, c, d;
- cin >> a >> b >> c >> d;
- a--; b--;
- graph[a].push_back(node(b, c, d));
- graph[b].push_back(node(a, c, d));
- }
- memset(visited, false, sizeof visited);
- int min_vreme = INF;
- queue<int> q;
- q.push(0);
- q.push(0);
- q.push(0);
- int sosed;
- int weight, money;
- int eee;
- while(!q.empty()){
- int teme = q.front();
- q.pop();
- int pari = q.front();
- q.pop();
- int pat = q.front();
- q.pop();
- if(teme == n - 1){
- if(pat <= S){
- min_vreme = min(min_vreme, pari);
- }
- continue;
- }
- for(int i = 0; i < (int)graph[teme].size(); i++){
- sosed = graph[teme][i].till;
- money = graph[teme][i].time;
- weight = graph[teme][i].euro;
- if(weight + pat <= S){
- eee = money + pari;
- if(eee >= 6000) eee -= 6000;
- if(!visited[sosed][eee]){
- visited[sosed][eee] = true;
- q.push(sosed);
- q.push(pari + money);
- q.push(pat + weight);
- }
- }
- }
- }
- q.push(0);
- q.push(0);
- q.push(0);
- memset(visited, false, sizeof visited);
- while(!q.empty()){
- int teme = q.front();
- q.pop();
- int pari = q.front();
- q.pop();
- int pat = q.front();
- q.pop();
- if(teme == n - 1){
- if(pat <= S){
- min_vreme = min(min_vreme, pari);
- }
- continue;
- }
- for(int i = 0; i < (int)graph[teme].size(); i++){
- sosed = graph[teme][i].till;
- money = graph[teme][i].time;
- weight = graph[teme][i].euro;
- if(weight + pat <= S){
- eee = pat + weight;
- if(eee >= 6000){
- eee -= 6000;
- }
- if(!visited[sosed][pat + weight]){
- visited[sosed][pat + weight] = true;
- q.push(sosed);
- q.push(pari + money);
- q.push(pat + weight);
- }
- }
- }
- }
- q.push(0);
- q.push(0);
- q.push(0);
- memset(idx, 0, sizeof idx);
- memset(visited, false, sizeof visited);
- while(!q.empty()){
- int teme = q.front();
- q.pop();
- int pari = q.front();
- q.pop();
- int pat = q.front();
- q.pop();
- if(teme == n - 1){
- if(pat <= S){
- min_vreme = min(min_vreme, pari);
- }
- continue;
- }
- for(int i = 0; i < (int)graph[teme].size(); i++){
- sosed = graph[teme][i].till;
- money = graph[teme][i].time;
- weight = graph[teme][i].euro;
- if(weight + pat <= S){
- eee = idx[sosed] + 1;
- if(eee >= 6000){
- eee -= 6000;
- }
- idx[sosed]++;
- if(!visited[sosed][pat + weight]){
- visited[sosed][pat + weight] = true;
- q.push(sosed);
- q.push(pari + money);
- q.push(pat + weight);
- }
- }
- }
- }
- if(min_vreme == INF){
- cout << -1 << endl;
- return 0;
- }
- cout << min_vreme << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement