fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4. #include <cstring>
  5.  
  6. using namespace std;
  7.  
  8. const int MAX =300000;
  9. const int QSIZE = 1000000;
  10.  
  11. int  a, b, c, h, i;
  12. vector<vector<int>> graph(MAX);
  13. vector<vector<long long>> peso(MAX);
  14. vector<int> gsize(MAX, 0);
  15. vector<int> gcapa(MAX, 1);
  16. vector<long long> D(MAX);
  17.  
  18.  
  19. void bfs(int partenza, int arrivo, vector<long long>& res) {
  20.     int qhead = 0, qcount = 1, first, second, j, k;
  21.     vector<int> q1(QSIZE), q2(QSIZE);
  22.     vector<bool> visited(MAX, false);
  23.  
  24.     q1[0] = partenza; 
  25.     q2[0] = 0;
  26.  
  27.     while (qcount > 0) {
  28.         first = q1[qhead];
  29.         second = q2[qhead];
  30.         qhead = (qhead + 1) % QSIZE;
  31.         qcount--;
  32.  
  33.         if (visited[first]) {
  34.             if (second < res[first]) {
  35.                 res[first] = second;
  36.             } else {
  37.                 continue;
  38.             }
  39.         }
  40.  
  41.         visited[first] = true;
  42.         res[first] = second;
  43.  
  44.         for (j = 0; j < gsize[first]; j++) {
  45.             q1[(qhead + qcount) % QSIZE] = graph[first][j];
  46.             q2[(qhead + qcount) % QSIZE] = second + peso[first][j];
  47.             qcount++;
  48.         }
  49.     }
  50. }
  51.  
  52. void mincammino(int N, int M, vector<int> S, vector<int> E, vector<int> P, vector<long long>& D) {
  53.     for (h = 0; h < N; h++) {
  54.         graph[h].resize(1);
  55.         peso[h].resize(1);
  56.         gsize[h] = 0;
  57.         gcapa[h] = 1;
  58.         D[h] = numeric_limits<long long>::max();
  59.     }
  60.  
  61.     for (h = 0; h < M; h++) {
  62.         a = S[h]; 
  63.         b = E[h]; 
  64.         c = P[h];
  65.         if (gsize[a] == gcapa[a]) {
  66.             gcapa[a] *= 2;
  67.             graph[a].resize(gcapa[a]);
  68.             peso[a].resize(gcapa[a]);
  69.         }
  70.         graph[a][gsize[a]] = b;
  71.         peso[a][gsize[a]] = c;
  72.         gsize[a]++;
  73.     }
  74.  
  75.     bfs(0, N - 1, D);
  76.     for (int k = 0; k < N; k++) {
  77.         if (D[k] == numeric_limits<long long>::max()) {
  78.             D[k] = -1;
  79.         }
  80.     }
  81. }
  82.  
  83. int main() {
  84.     int N, M;
  85.     cin >> N >> M;
  86.  
  87.     vector<int> X(M), Y(M), P(M);
  88.     vector<long long> D(N);
  89.  
  90.     for (int i = 0; i < M; i++) {
  91.         cin >> X[i] >> Y[i] >> P[i];
  92.     }
  93.  
  94.     mincammino(N, M, X, Y, P, D);
  95.  
  96.     for (int i = 0; i < N; i++) {
  97.         cout << D[i] << ' ';
  98.     }
  99.     cout << '\n';
  100. }
  101.  
Success #stdin #stdout 0.01s 29920KB
comments (?)
stdin
copy 
2 1
1 0 1
stdout
copy 
0 -1
https://ideone.com/ARBHfE
language:
C++ (gcc 8.3)
created:
11 days 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!