fork download
copy 
  1. #include<cstdio>
  2. #include<vector>
  3. #include<queue>
  4.  
  5. using namespace std;
  6.  
  7. int dis[100],vis[100];
  8. vector <pair <int,int> > adj[100];
  9. priority_queue < pair<int,int> ,vector <pair <int,int> >, greater <pair <int,int> > > pq;
  10.  
  11. int dijkstra(int s,int des)
  12. {
  13.     int i;
  14.     for(i=0;i<100;i++)
  15.         dis[i]=1000000000;
  16.     dis[s]=0;
  17.     vis[s]=1;
  18.     pair <int,int> tp;
  19.     tp.first=0;
  20.     tp.second=s;
  21.     pq.push(tp);
  22.     printf("-\n");
  23.     while(!pq.empty())
  24.     {
  25.         printf("*\n");
  26.         tp=pq.top();
  27.         pq.pop();
  28.         vis[tp.second]=1;
  29.         printf("%d-> %d\n",tp.second,tp.first);
  30.         int u=tp.second;
  31.         printf("%d--\n",(int)adj[u].size());
  32.         for(i=0;i<adj[u].size();i++)
  33.         {
  34.             int v=adj[u][i].second;
  35. //            printf("%d*-> %d\n",adj[u][i].second,adj[u][i].first);
  36.             if(!vis[v])
  37.             {
  38.                 if(dis[u]+adj[u][i].first<dis[v])
  39.                 {
  40.                     dis[v]=dis[u]+adj[u][i].first;
  41.                     pair <int,int> nw;
  42.                     nw.first=dis[v];
  43.                     nw.second=v;
  44.                     pq.push(nw);
  45.  
  46.                 }
  47.             }
  48.         }
  49.     }
  50.     return dis[des];
  51. }
  52.  
  53. int main()
  54. {
  55.     int v,i,j,p,c,w,b,e;
  56.     pair <int,int> cw;
  57.     scanf("%d",&v);
  58.     while(scanf("%d%d%d",&p,&c,&w)!=EOF)
  59.     {
  60.         cw.first=w;
  61.         cw.second=c;
  62.         adj[p].push_back(cw);
  63.         cw.first=w;
  64.         cw.second=p;
  65.         adj[c].push_back(cw);
  66.     }
  67.     for(i=1;i<=v;i++)
  68.     {
  69.         printf("\n%d->\n",i);
  70.         for( j=0;j<adj[i].size();j++)
  71.         {
  72.             printf("%d %d\n",adj[i][j].second,adj[i][j].first);
  73.         }
  74.     }
  75.     scanf("%d%d",&b,&e);
  76.     printf("%d",dijkstra(b,e));
  77. }
  78.  
  79. /*
  80. input-
  81.  
  82. 9
  83. 1 2 4
  84. 1 8 8
  85. 2 8 11
  86. 2 3 8
  87. 8 7 1
  88. 8 9 7
  89. 3 4 7
  90. 3 9 2
  91. 3 6 4
  92. 9 7 6
  93. 7 6 2
  94. 4 6 14
  95. 4 5 9
  96. 6 5 10
  97.  
  98. 1 5
  99.  
  100. output- 21
  101.  
  102. */
  103.  
Success #stdin #stdout 0s 4212KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-
*
2-> 0
0--
1000000000
https://ideone.com/KSMNAU
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!