SHARE
TWEET

Untitled

a guest Sep 22nd, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define INF     1e7
  5.  
  6. vector< pair<int,int> >edges[101];
  7. int dis[101],n;
  8.  
  9. void dijkstra()
  10. {
  11.     int i;
  12.     for(i=1;i<=n;i++)
  13.         dis[i]=INF;
  14.     dis[1]=0;
  15.     priority_queue < pair<int,int> , vector< pair<int,int> > , greater < pair<int,int> > > pq;
  16.     pq.push(make_pair(dis[1],1));
  17.     while(!pq.empty())
  18.     {
  19.         int u = pq.top().second;
  20.         pq.pop();
  21.         for(int i=0;i<edges[u].size();i++)
  22.         {
  23.             int v = edges[u][i].first;
  24.             int w = edges[u][i].second;
  25.             if(dis[v]>dis[u]+w)
  26.             {
  27.                 dis[v]=dis[u]+w;
  28.                 pq.push(make_pair(dis[v],v));
  29.             }
  30.         }
  31.     }
  32.     return;
  33. }
  34.  
  35. int main()
  36. {
  37.     int t,i,j,k,l,m,u,v,w;
  38.     scanf("%d",&t);
  39.     for(i=1;i<=t;i++)
  40.     {
  41.         scanf("%d%d",&n,&m);
  42.         for(j=1;j<=n;j++)
  43.             edges[j].clear();
  44.         for(j=0;j<m;j++)
  45.         {
  46.             scanf("%d%d%d",&u,&v,&w);
  47.             edges[u].push_back(make_pair(v,w));
  48.             edges[v].push_back(make_pair(u,w));
  49.         }
  50.         dijkstra();
  51.         if(dis[n]==INF)
  52.             printf("Case %d: Impossible\n",i);
  53.         else
  54.             printf("Case %d: %d\n",i,dis[n]);
  55.     }
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top