fork download 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <math.h>
  4. #include <stdlib.h>
  5.  
  6. #define MAX 1000
  7. #define INF 100000000
  8.  
  9. typedef struct {
  10.     int to;
  11.     int weight;
  12. }Edge;
  13.  
  14. Edge adj[MAX][MAX];
  15. int edgeCount[MAX];
  16.  
  17. int dist[MAX];
  18. int visited[MAX];
  19. int n, m;
  20.  
  21. void dijkstra(int start){
  22.     for(int i=0; i<n; i++){
  23.         dist[i] = INF;
  24.         visited[i] = 0;
  25.     }
  26.  
  27.     dist[start] = 0;
  28.  
  29.     for(int i=0; i<n; i++){
  30.         int u = -1;
  31.  
  32.         // Pick the unvisted node with the smallest distance
  33.  
  34.         for(int j=0; j<n; j++){
  35.             if(!visited[j] && (u == -1 || dist[j] < dist[u])){
  36.                 u = j;
  37.             }
  38.         }
  39.  
  40.         if(dist[u] == INF) break; // Remaining nodes are unreachable
  41.         visited[u] = 1;
  42.  
  43.         //Relax edges
  44.         for(int k=0; k<edgeCount[u]; k++){
  45.             int v = adj[u][k].to;
  46.             int w = adj[u][k].weight;
  47.  
  48.             if(dist[u] +w <dist[v]){
  49.                 dist[v] = dist[u]+w;
  50.             }
  51.         }
  52.     }
  53. }
  54.  
  55. int main() {
  56.  
  57.     scanf("%d %d",&n, &m);
  58.     //Read all edges
  59.     for(int i=0; i<m; i++){
  60.         int u, v, w;
  61.         scanf("%d %d %d", &u, &v, &w);
  62.         adj[u][edgeCount[u]].to = v;
  63.         adj[u][edgeCount[u]].weight = w;
  64.         edgeCount[u]++;
  65.     }
  66.  
  67.     int start, end;
  68.     scanf("%d %d", &start, &end);
  69.      dijkstra(start);
  70.  
  71.      if(dist[end] == INF)
  72.         printf("-1\n");
  73.      else
  74.         printf("%d\n",dist[end]);
  75.     /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
  76.     return 0;
  77. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
5 6
0 1 2
0 2 4
1 2 1
1 3 7
2 4 3
3 4 1
0
stdout 
6
https://ideone.com/NaPFnH
language:
C (clang 8.0)
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!