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