fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #define INF 987654321
  4. #define TAM 10100
  5. using namespace std;
  6.  
  7. vector<int> dist(TAM, INF);
  8. //vector<int> pred(TAM, INF);
  9. vector<int> dist_i(TAM, INF);
  10. //vector<int> pred_i(TAM, INF);
  11.  
  12. void BF(vector<vector<pair<int,int> > > &g, int v);
  13.  
  14. int main(){
  15.   int v, a, from, to, peso;
  16.     cin>>v>>a;
  17.     vector<vector<pair<int,int> > > g(TAM);
  18.     while(a--){
  19.       cin>>from>>to>>peso; from--; to--;
  20.       g[from].push_back(make_pair(to, peso));
  21.       g[to].push_back(make_pair(from, peso));
  22.     }
  23.     dist[0]=0;
  24.     BF(g, v);
  25.     int aux=dist[v-1];
  26.     if(aux!=INF)
  27.       cout<<aux<<endl;
  28.     else
  29.       cout<<"-1"<<endl;
  30.     g.clear(); dist.clear(); dist_i.clear(); //pred.clear(); pred_i.clear();
  31. }
  32.  
  33. void BF(vector<vector<pair<int,int> > > &g, int v){
  34.   for(int k=0; k<v; k++)
  35.     for(int i=0; i<v; i++)
  36.       if(dist[i]!=INF or dist_i[i]!=INF)
  37.         for(int j=0; j<g[i].size(); j++){
  38.           int vert=g[i][j].first;
  39.           if(dist[vert]>dist_i[i]+g[i][j].second){
  40.             dist[vert]=dist_i[i]+g[i][j].second;
  41.             //pred[vert]=i;
  42.           }
  43.           if(dist_i[vert]>dist[i]+g[i][j].second){
  44.             dist_i[vert]=dist[i]+g[i][j].second;
  45.             //pred_i[vert]=i;
  46.           }
  47.         }
  48. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5 5
1 2 1
2 3 1
3 4 1
4 2 1
1 5 1
stdout
copy 
6
https://ideone.com/YYoqn2
language:
C++14 (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!