fork(5) download
copy 
  1. //
  2. //  main.cpp
  3. //  Traktor
  4. //
  5. //  Created by Jędrzej Dudzicz on 23.04.2017.
  6. //  Copyright © 2017 Jędrzej Dudzicz. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <cstdio>
  11. #include <queue>
  12. #include <vector>
  13. #include <utility>
  14. #include <algorithm>
  15. #include <cmath>
  16. using namespace std;
  17. bool odwiedzone[200006];
  18. int odleglosc[200006];
  19. int wypisz[200006];
  20. priority_queue<pair<int,int> >kolejka;
  21. vector<pair<int,int> > tablica[200006];
  22.  
  23. int k=0;
  24. void dfs(int v){
  25.     wypisz[k]=v;
  26.     k++;
  27.     for(int i=0;i<tablica[v].size();++i){
  28.         int t1 = tablica[v][i].first;//odleglosc
  29.         int t2 = tablica[v][i].second;//sasiad
  30.         if(odwiedzone[t2]==0&&odleglosc[v]==(odleglosc[t2]+t1)){
  31.             odwiedzone[t2]=1;
  32.             dfs(t2);
  33.         }
  34.     }
  35. }
  36. void Dikstra(){
  37.     for(int i=1;i<=200005;++i)odleglosc[i]=1000000005;
  38.     int wierzcholki,krawedzie,a,b,waga,index;
  39.     scanf("%d%d",&wierzcholki,&krawedzie);
  40.  
  41.     for(int i=0;i<krawedzie;++i){
  42.         scanf("%d%d%d",&a,&b,&waga);
  43.         tablica[a].push_back(make_pair(waga,b));
  44.         tablica[b].push_back(make_pair(waga,a));
  45.  
  46.     }
  47.     odleglosc[1]=0;
  48.     kolejka.push(make_pair(0,1));
  49.     while(!kolejka.empty()){
  50.         index=kolejka.top().second;
  51.         kolejka.pop();
  52.         if(odwiedzone[index]==0){
  53.             odwiedzone[index]=1;
  54.             for(int i=0;i<tablica[index].size();++i){
  55.                 int t1 = tablica[index][i].first;
  56.                 int t2 = tablica[index][i].second;
  57.                 if(odleglosc[t2]>odleglosc[index]+t1){
  58.                     odleglosc[t2]=odleglosc[index]+t1;
  59.                     kolejka.push(make_pair((-t1),t2));
  60.                 }
  61.             }
  62.         }
  63.     }
  64.     for(int i=1;i<=200005;++i)odwiedzone[i]=0;
  65.     odwiedzone[wierzcholki]=1;
  66.  
  67.     dfs(wierzcholki);
  68.     sort(wypisz,wypisz+k);
  69.     for(int i=0;i<k;++i){
  70.         printf("%d\n",wypisz[i]);
  71.     }
  72.     for(int i=1;i<=wierzcholki;++i){
  73.         printf("%d ",odleglosc[i]);
  74.     }
  75. }
  76. int main(){
  77.     Dikstra();
  78.     return 0;
  79. }
  80.  
  81.  
  82.  
Success #stdin #stdout 0s 21688KB
comments (?)
stdin
copy 
6 6
1 2 5
2 3 5
3 4 5
1 5 6
5 4 6
4 6 1
stdout
copy 
6
0 5 10 12 6 16
https://ideone.com/QO9hXj
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!