fork(5) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define INP "input.inp"
  4. #define OUT "output.out"
  5. int main()
  6. {
  7. 	FILE *f = fopen(INP, "r");
  8. 	int n, a, b, i, sum = 0;
  9. 	fscanf(f,"%d%d%d", &n, &a, &b);
  10. 	int G[n][n];
  11. 	int s[n], Len[n], P[n];
  12.  
  13. 	for (i = 0; i<n; i++)		// nhap ma tran 
  14. 		for (int j=0; j<n; j++)
  15. 		{
  16. 			fscanf(f, "%d", &G[i][j]);
  17. 			sum += G[i][j];
  18. 		}
  19. 	for (int i=0; i<n; i++)		// dat vo cung bang tong gia tri ma tran
  20. 	{
  21. 		for (int j=0; j<n; j++)
  22. 		{
  23. 			printf("%3d", G[i][j]);
  24. 			if (G[i][j] == 0) G[i][j] = sum;
  25. 		}
  26. 		printf("\n");
  27. 	}
  28.  
  29. 	for (int i=0; i<n; i++)
  30. 	{
  31. 		Len[i] = sum;		// do dai den diem i
  32. 		s[i] = 0;			// danh sach cac diem da xet
  33. 		P[i] = a;			// dat diem bat dau cua moi diem la a
  34. 	}
  35.  
  36. 	Len[a] = 0;				// dat do dai tu a -> a la 0
  37.  
  38. 	while (s[b] == 0)		// trong khi diem cuoi chua duoc xet
  39. 	{
  40. 		for (i=0; i<n; i++)	// tim 1 vi tri ma khong phai la vo cung
  41. 			if (!s[i] && Len[i] < sum)
  42. 				break;
  43. 		if (i >= n) break;
  44. 		for (int j=0; j<n; j++)	// tim diem co vi tri ma do dai la min
  45. 			if (!s[j] && Len[i] > Len[j])
  46. 				i = j;
  47.  
  48. 		s[i] = 1;	// cho i vao danh sach xet roi
  49. 		for (int j=0; j<n; j++)	// dubet tinh lai do dai cua cac diem chua xet
  50. 			if (!s[j] && Len[i] + G[i][j] < Len[j])
  51. 			{
  52. 				Len[j] = Len[i] + G[i][j];	// thay doi len
  53. 				P[j] = i;	// danh dau diem truoc no
  54. 			}
  55. 	}
  56.  
  57. 	printf("\nLength of %d to %d is %d\n",a, b, Len[b]);
  58.  
  59. 	// truy vet
  60. 	i = b;
  61. 	while (i != a)
  62. 	{
  63. 		printf("%d <-- ", i);
  64. 		i = P[i];
  65. 	}
  66. 	printf("%d", a);
  67.  
  68. 	return 0;
  69. }
  70.  
Runtime error #stdin #stdout 0s 2812KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zZmmog
Dijkstra cũ
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!