fork(3) download
  1. #include <stdio.h>
  2. #include <limits.h>
  3.  
  4. #define INF INT_MAX
  5. int N;
  6. int Dist[500];
  7. int Q[500];
  8. int Visited[500];
  9. int Graph[500][500];
  10.  
  11. void Dijkstra(int b){
  12. int H = 0;
  13. int T = -1;
  14. int j,k;
  15.  
  16. Dist[b] = 0;
  17.  
  18. Q[T+1] = b;
  19. T = T+1;
  20.  
  21. while(T>=H){
  22. j = Q[H];
  23. Visited[j] = 1;
  24. for (k = 0;k < N; k++){
  25. if(!Visited[k] && Dist[k] > Graph[j][k] + Dist[j] && Graph[j][k] != -1){
  26. Dist[k] = Dist[j]+Graph[j][k];
  27. Q[T+1] = k;
  28. T = T+1;
  29. }
  30. }
  31.  
  32. H = H+1;
  33. }
  34. }
  35.  
  36. int main(){
  37.  
  38. int src,target,m;
  39. int a,w,b,i,j;
  40.  
  41. scanf("%d%d%d%d",&N,&m,&src,&target);
  42.  
  43. for(i = 0;i < N;i ++){
  44. for(j = 0;j < N;j++){
  45. Graph[i][j] = -1;
  46. }
  47. }
  48.  
  49. for(i = 0; i< N; i++){
  50. Dist[i] = INF;
  51. Visited[i] = 0;
  52. }
  53.  
  54.  
  55. for(i = 0;i < m; i++){
  56. scanf("%d%d%d",&a,&b,&w);
  57. a--;
  58. b--;
  59. Graph[a][b] = w;
  60. Graph[b][a] = w;
  61. }
  62.  
  63. Dijkstra(src-1);
  64.  
  65.  
  66. if(Dist[target-1] == INF){
  67. printf("NO");
  68. }else {
  69. printf("YES\n%d",Dist[target-1]);
  70. }
  71.  
  72. return 0;
  73. }
Success #stdin #stdout 0.01s 2660KB
stdin
8 9 1 3
1 5 6
5 3 2
1 2 7
2 3 2
1 4 7
4 3 1
1 7 3
7 8 2
8 3 2
stdout
YES
8