fork download
copy 
  1. /*
  2. 実行後の入力形式は
  3. ------------------------------
  4. 頂点数 辺数
  5. 始点 終点 コスト
  6. 始点 終点 コスト
  7. ...(辺の本数分だけ入力)
  8. (最短距離を求めたい)始点 終点
  9. ------------------------------
  10. です.
  11.  
  12. 例
  13. $ gcc -o cycle cycle.c
  14. $ cycle.exe
  15. 7 10
  16. 0 1 30
  17. 0 3 10
  18. 0 2 15
  19. 1 3 25
  20. 1 4 60
  21. 2 3 40
  22. 2 5 20
  23. 3 6 35
  24. 4 6 20
  25. 5 6 30
  26. 0 6
  27. distance:45
  28. 6 -> 3 -> 0
  29.  
  30. */
  31.  
  32. #include <stdio.h>
  33.  
  34. #define INF 10000000
  35. #define SIZE 1000
  36. #define TRUE 1
  37. #define FALSE 0
  38.  
  39. int DIST[SIZE][SIZE];
  40. int COST[SIZE];
  41. int VIA[SIZE];
  42. int N;
  43. char USED[SIZE];
  44.  
  45. int dijkstra(int start, int goal)
  46. {
  47.   int min, target;
  48.  
  49.   COST[start] = 0;
  50.  
  51.   while (1)
  52.   {
  53.  
  54.     /* 未確定の中から距離が最も小さい地点(a)を選んで、その距離を その地点の最小距離として確定します */
  55.     min = INF;
  56.     for (int i = 0; i < N; i++)
  57.     {
  58.       if (!USED[i] && min > COST[i])
  59.       {
  60.         min = COST[i];
  61.         target = i;
  62.       }
  63.     }
  64.  
  65.     /* 全ての地点の最短経路が確定 */
  66.     if (target == goal)
  67.       return COST[goal];
  68.  
  69.     /* 今確定した場所から「直接つながっている」かつ「未確定の」地点に関して、
  70.     今確定した場所を経由した場合の距離を計算し、今までの距離よりも小さければ書き直します。 */
  71.     for (int neighboring = 0; neighboring < N; neighboring++)
  72.     {
  73.       if (COST[neighboring] > DIST[target][neighboring] + COST[target])
  74.       {
  75.         COST[neighboring] = DIST[target][neighboring] + COST[target];
  76.         VIA[neighboring] = target;
  77.       }
  78.     }
  79.     USED[target] = TRUE;
  80.   }
  81. }
  82.  
  83. int main(void)
  84. {
  85.   int r;
  86.   int a, b, l;
  87.   int s, d;
  88.  
  89.   /* 初期化 */
  90.   for (int i = 0; i < SIZE; i++)
  91.   {
  92.     COST[i] = INF;
  93.     USED[i] = FALSE;
  94.     VIA[i] = -1;
  95.     for (int j = 0; j < SIZE; j++)
  96.       DIST[i][j] = INF;
  97.   }
  98.  
  99.   /* 入力 */
  100.   scanf("%d %d", &N, &r);
  101.   for (int i = 0; i < r; i++)
  102.   {
  103.     scanf("%d %d %d", &a, &b, &l);
  104.     DIST[a][b] = l;
  105.   }
  106.   scanf("%d %d", &s, &d);
  107.  
  108.   /* ダイクストラ法で最短経路を求める */
  109.   printf("distance:%d\n", dijkstra(s, d));
  110.  
  111.   /* 経路を表示(ゴールから) */
  112.   int node = d;
  113.   printf("%d", node);
  114.   while (1)
  115.   {
  116.     node = VIA[node];
  117.     printf(" -> %d", node);
  118.     if (node == s)
  119.       break;
  120.   }
  121.  
  122.   return 0;
  123. }
Runtime error #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bXF0iQ
language:
C (gcc 8.3)
created:
4 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!