Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <algorithm>
- using namespace std ;
- struct node{
- int index,najmal_pat,money;
- node(int i,int p,int m){
- index = i;
- najmal_pat = p;
- money = m;
- }
- bool operator < (const node &tmp)const {
- return najmal_pat > tmp.najmal_pat;
- }
- };
- int dist[3005][2005];
- int main() {
- int S, N , M;
- cin >> S >> N >> M;
- vector<node> graph[N+5];
- for (int i = 0; i < M; i++) {
- int v,w,t,e;
- cin >> v >> w >> t >> e;
- graph[v].push_back(node(w,t,e));
- graph[w].push_back(node(v,t,e));
- }
- priority_queue<node> pq;
- pq.push(node(1,0,0));
- for (int i = 0; i < 3005; i++) {
- for (int j = 0; j < 2005; j++) {
- dist[i][j] = 2e9;
- }
- }
- dist[1][0] = 0;
- while(!pq.empty()){
- node current = pq.top();
- pq.pop();
- for (int i = 0; i < graph[current.index].size(); i++) {
- int sosed = graph[current.index][i].index;
- int pat = graph[current.index][i].najmal_pat;
- int pari = graph[current.index][i].money;
- if(pari+current.money <= S && current.najmal_pat + pat < dist[sosed][pari+current.money]){
- dist[sosed][pari + current.money] = current.najmal_pat + pat;
- pq.push(node(sosed,current.najmal_pat +pat,current.money + pari));
- }
- }
- }
- int rezultat= 2e9;
- for (int i = 0; i <= S; i++) {
- rezultat = min(dist[N][i], rezultat);
- }
- if (rezultat == 2e9){
- cout << "-1";
- }
- else
- cout << rezultat << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement