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 index;
- int cost;
- int snow;
- node(){
- }
- node( int _index, int _cost, int _snow){
- index=_index;
- cost=_cost;
- snow=_snow;
- }
- bool operator < (const node&tmp) const{
- return cost>tmp.cost;
- }
- };
- int main()
- {
- int N;
- int M;
- cin>>N>>M;
- vector<node> v[N + 1];
- for(int x=0; x<M; x++){
- int a;
- int b;
- int c;
- int d;
- cin>>a>>b>>c>>d;
- v[a].push_back(node(b, c, d));
- v[b].push_back(node(a, c, d));
- }
- priority_queue<node>pq;
- pq.push(node(1, 0, 1));
- bool matrica[N + 1];
- for(int x1=0; x1 <= N; x1++){
- matrica[x1]=false;
- }
- while(!pq.empty()){
- node c=pq.top();
- pq.pop();
- matrica[c.index]=true;
- if(c.index==N){
- cout<<c.cost<<endl;
- if(c.snow==1){
- cout<<"DA";
- }
- else{
- cout<<"NE";
- }
- return 0;
- }
- for(int i=0; i<v[c.index].size(); i++){
- int sosed=v[c.index][i].index;
- int snow1=v[c.index][i].snow;
- int pat=v[c.index][i].cost;
- if((c.snow==1)and(snow1==1)and(matrica[sosed]==false)){
- pq.push(node(sosed, pat+c.cost, 1));
- }
- else if(matrica[sosed]==false){
- pq.push(node(sosed, pat+c.cost, 0));
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement