Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include<fstream>
- #include<vector>
- #include<fstream>
- #include<algorithm>
- #include<cmath>
- #define Nmax 20000002
- typedef int coada[30001];
- using namespace std;
- ifstream f("sate.in");
- ofstream g("sate.out");
- int cst[30001],n,m,x,y,i,j,cost,q,k,l;
- coada c;
- vector<pair <int,int> >v[30001];
- inline void BFS(int nod)
- {
- cst[nod]=0;
- int siz=1,start=1;
- c[start]=nod;
- while(siz>=start)
- {
- int k=c[start];
- for(int i=0;i<v[k].size();i++)
- if(cst[v[k][i].first]>cst[k]+v[k][i].second)
- {
- cst[v[k][i].first]=cst[k]+v[k][i].second;
- siz++;
- c[siz]=v[k][i].first;
- }
- start++;
- }
- }
- int main()
- {
- f>>n>>m>>x>>y;
- for(q=1;q<=m;q++)
- {
- f>>i>>j>>cost;
- v[i].push_back(make_pair(j,cost));
- v[j].push_back(make_pair(i,cost));
- for(k=0;k<v[i].size()-1;k++)
- for(l=1;l<v[i].size();l++)
- {
- if(binary_search(v[v[i][k].first].begin(),v[v[i][k].first].end(),v[i][l].first))
- {v[v[i][k].first].push_back(make_pair(v[i][l].first,abs( v[i][k].second-v[i][l].second )));
- v[v[i][l].first].push_back(make_pair(v[i][k].first,abs( v[i][k].second-v[i][l].second )));}
- }
- for(k=0;k<v[j].size()-1;k++)
- for(l=1;l<v[j].size();l++)
- {
- if(binary_search(v[v[j][k].first].begin(),v[v[j][k].first].end(),v[j][l].first))
- {v[v[j][k].first].push_back(make_pair(v[j][l].first,abs( v[j][k].second-v[j][l].second )));
- v[v[j][l].first].push_back(make_pair(v[j][k].first,abs( v[j][k].second-v[j][l].second )));}
- }
- }
- for(i=1;i<=n;i++)
- cst[i]=Nmax;
- BFS(x);
- g<<cst[y];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement