Guest User

Untitled

a guest
Jul 15th, 2018
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.91 KB | None | 0 0
  1. #include <stdio.h>
  2. #define MAX 100
  3. #define INF 1000000000
  4.  
  5. int main()
  6. {
  7. FILE *inp=fopen("input.txt", "r");
  8. FILE *out=fopen("output.txt", "w");
  9. int A[MAX][MAX];
  10. int path[MAX];
  11. int used[MAX]={0};
  12. int i, j, n, snd, rcv, t1, t2, t3, min, curr;
  13. fscanf(inp, "%d\n%d %d", &n, &snd, &rcv);
  14. for(i=1;i<=n;i++)
  15. {
  16. path[i]=INF;
  17. for(j=1;j<=n;j++) A[i][j]=INF;
  18. }
  19. path[snd]=0;
  20. while(fscanf(inp, "%d %d %d", &t1, &t2, &t3)!=EOF)
  21. {
  22. A[t1][t2]=t3;
  23. A[t2][t1]=t3;
  24. }
  25. while(1)
  26. {
  27. min=INF;
  28. for(i=1;i<=n;i++)
  29. {
  30. if(!used[i] && (path[i]<min))
  31. {
  32. min=path[i];
  33. curr=i;
  34. }
  35. }
  36. if(min==INF) break;
  37. used[curr]=1;
  38. for (i=1;i<=n;i++)
  39. {
  40. if(used[i]) continue;
  41. if(path[i]>(path[curr]+A[curr][i])) path[i]=(path[curr]+A[curr][i]);
  42. }
  43. }
  44. if(path[rcv]==INF) fprintf(out, "no\n"); else fprintf(out, "%d\n", path[rcv]);
  45. fclose(inp);
  46. fclose(out);
  47. return 0;
  48. }
Add Comment
Please, Sign In to add comment