Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<vector>
- #include<queue>
- using namespace std;
- typedef long long int ll;
- struct edge{
- int v;
- ll w;
- bool operator < (const edge& rhs)const
- {
- return w > rhs.w;
- }
- };
- int main()
- {
- int n,m;
- scanf("%d %d",&n,&m);
- vector<edge> adj[n+1];
- for(int i = 0 ; i < m ; i ++){
- int u,v;
- ll w;
- scanf("%d %d %lld",&u,&v,&w);
- adj[u].push_back({v,w});
- adj[v].push_back({u,w});
- }
- int a,b;
- scanf("%d %d",&a,&b);
- ll distA[n+1];
- ll distB[n+1];
- ll distC[n+1];
- bool visitedA[n+1];
- bool visitedB[n+1];
- bool visitedC[n+1];
- bool check[n+1];
- for(int i = 0 ; i <= n ; i ++){
- distA[i] = 1e18;
- distB[i] = 1e18;
- distC[i] = 1e18;
- visitedA[i] = false;
- visitedB[i] = false;
- visitedC[i] = false;
- check[i] = true;
- }
- priority_queue<edge> pq;
- distA[a] = 0;
- pq.push({a,distA[a]});
- while(!pq.empty()){
- int u = pq.top().v;
- pq.pop();
- if(visitedA[u])continue;
- visitedA[u] = true;
- for(int i = 0 ; i < adj[u].size() ; i ++){
- int v = adj[u][i].v;
- ll w = adj[u][i].w;
- if(!visitedA[v] && distA[u] + w < distA[v]){
- distA[v] = distA[u] + w;
- pq.push({v,distA[v]});
- }
- }
- }
- /* printf("distA : ");
- for(int i = 1 ; i <= n ; i ++){
- printf("%lld ",distA[i]);
- }
- printf("\n");*/
- distB[b] = 0;
- pq.push({b,distB[b]});
- while(!pq.empty()){
- int u = pq.top().v;
- pq.pop();
- // printf("Test dijstraB u #%d\n",u);
- if(visitedB[u])continue;
- visitedB[u] = true;
- for(int i = 0 ; i < adj[u].size() ; i ++){
- int v = adj[u][i].v;
- ll w = adj[u][i].w;
- if(!visitedB[v] && distB[u] + w < distB[v]){
- distB[v] = distB[u] + w;
- pq.push({v,distB[v]});
- }
- }
- }
- /* printf("distB : ");
- for(int i = 1 ; i <= n ; i ++){
- printf("%lld ",distB[i]);
- }
- printf("\n");*/
- for(int i = 1 ; i <= n ; i ++){
- if(distA[i] + distB[i] == distA[b]){
- check[i] = false;
- // printf("Test checked %d\n",i);
- }
- }
- int c,d;
- scanf("%d %d",&c,&d);
- distC[c] = 0;
- pq.push({c,distC[c]});
- while(!pq.empty()){
- int u = pq.top().v;
- pq.pop();
- if(visitedC[u] || !check[u])continue;
- visitedC[u] = true;
- for(int i = 0 ; i < adj[u].size() ; i ++){
- int v = adj[u][i].v;
- ll w = adj[u][i].w;
- if(check[v] && !visitedC[v] && distC[u] + w < distC[v]){
- distC[v] = distC[u] + w;
- pq.push({v,distC[v]});
- }
- }
- }
- printf("%lld",(distC[d] == 1e18 ? -1 : distC[d]));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement