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 idx;
- int distance;
- int money;
- node(){}
- node(int _idx, int _distance, int _money)
- {
- idx=_idx;
- distance=_distance;
- money=_money;
- }
- bool operator < (const node &tmp) const{
- return distance > tmp.distance;
- }
- };
- int main()
- {
- int s;
- int n,m;
- cin>>s>>n>>m;
- vector<node>v[n+1];
- for(int i=0; i<m;i++)
- {
- int a,b,c,d;
- cin>>a>>b>>c>>d;
- v[a].push_back(node(b,c,d));
- v[b].push_back(node(a,c,d));
- }
- int dis[n+1][s+1];
- for(int i=0;i<n+1;i++)
- {
- for(int j=0;j<s+1;j++)
- {
- dis[i][j]=2e9;
- }
- }
- priority_queue<node>pq;
- pq.push(node(1,0,0));
- while(!pq.empty())
- {
- node c=pq.top();
- pq.pop();
- for(int i=0;i< v[c.idx].size(); i++)
- {
- int sosed = v[c.idx][i].idx;
- int d = v[c.idx][i].distance;
- int pari= v[c.idx][i].money;
- if(pari+c.money<=s)
- {
- if(d+c.distance<dis[sosed][pari+c.money])
- {
- pq.push(node(sosed, d+c.distance,pari+c.money));
- dis[sosed][pari+c.money]=d+c.distance;
- }
- }
- }
- }
- int rez=2e9;
- for(int i=0;i<=s;i++)
- {
- rez=min(rez,dis[n][i]);
- }
- if(rez==2e9)
- cout<<-1;
- else
- cout<<rez;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement