Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- struct node{
- int distance;
- int cena;
- int index;
- node(){
- }
- node(int _index, int _distance, int _cena){
- index=_index;
- distance=_distance;
- cena=_cena;
- }
- bool operator <(const node&tmp)const{
- return distance > tmp.distance;
- }
- };
- int main()
- {
- int n;
- int m;
- int S;
- int S1=200000000;
- cin>>S;
- cin>>n>>m;
- int matrica[n+1][S + 1];
- vector<node>v[n+1];
- for(int x1=0; x1<n+1; x1++){
- for(int s1=0; s1<= S; s1++){
- matrica[x1][s1]=2000000000;
- }
- }
- for(int x=0; x<m; x++){
- int indexa;
- int indexb;
- int distance;
- int cost;
- cin>>indexa>>indexb>>distance>>cost;
- v[indexa].push_back(node(indexb, distance, cost));
- v[indexb].push_back(node(indexa, distance, cost));
- }
- priority_queue<node>pq;
- pq.push(node(1, 0, 0));
- matrica[1][0]=0;
- while(!pq.empty()){
- node cnode=pq.top();
- pq.pop();
- for(int h=0; h<v[cnode.index].size(); h++){
- int sosed=v[cnode.index][h].index;
- int distance=v[cnode.index][h].distance;
- int cena=v[cnode.index][h].cena;
- if((cena+cnode.cena<=S)and(matrica[sosed][cena+cnode.cena]>distance+cnode.distance)){
- matrica[sosed][cena+cnode.cena]=distance+cnode.distance;
- pq.push(node(sosed, distance+cnode.distance, cena+cnode.cena));
- }
- }
- }
- for(int y=0; y<=S; y++){
- if(matrica[n][y]<S1){
- S1=matrica[n][y];
- }
- }
- if(S1 == 200000000) {
- S1 = -1;
- }
- cout<<S1;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement