fork download
copy 
  1. #include <stdio.h>
  2. #define oo 999
  3. typedef struct{
  4. 	int n;
  5. 	int A[100][100];
  6. }Graph;
  7. void init_graph(Graph *G, int n){
  8. 	G->n = n;
  9. 	for(int u=1;u<=G->n;u++){
  10. 		for(int v=1;v<=G->n;v++){
  11. 			G->A[u][v] = 0;
  12. 		}
  13. 	}
  14. }
  15. void add_edge(Graph *G, int u, int v, int w){
  16. 	G->A[u][v] = w;
  17. }
  18. int mark[100];
  19. int pi[100];
  20. int p[100];
  21. int cnt[100];
  22. void MooreDijkstra(Graph *G, int s){
  23. 	int u,v,it;
  24. 	for(u=1;u<=G->n;u++){
  25. 		pi[u] = oo;
  26. 		mark[u] = 0;
  27. 		cnt[u] = 0;
  28. 	}
  29. 	pi[s] = 0;
  30. 	p[s] = 1;
  31. 	cnt[s] = 1;
  32. 	for(it=1;it<G->n;it++){
  33. 		int j, min_pi=oo;
  34. 		for(j=1;j<=G->n;j++){
  35. 			if(mark[j]==0 && pi[j] < min_pi){
  36. 				min_pi = pi[j];
  37. 				u = j;
  38. 			}
  39. 		}
  40. 		mark[u] = 1;
  41.  
  42. 		for(v=1;v<=G->n;v++){
  43. 			if(G->A[u][v] != 0 && mark[v]==0){
  44. 				if(pi[u] + G->A[u][v] < pi[v]){
  45. 					pi[v] = pi[u] + G->A[u][v];
  46. 					cnt[v]=cnt[u];
  47. 					p[v] = u;
  48. 				}
  49. 				else if(pi[u] + G->A[u][v] == pi[v]){
  50. 					cnt[v] += cnt[u];
  51. 				}
  52. 			}
  53. 		}
  54. 	}
  55. }
  56. int main(){
  57. 	Graph G;
  58. 	int n, m, u, v, w, e;
  59. 	scanf("%d%d", &n, &m);
  60. 	init_graph(&G, n);
  61.  
  62. 	for (e = 0; e < m; e++) {
  63. 		scanf("%d%d%d", &u, &v, &w);
  64. 		add_edge(&G, u, v, w);
  65. 	}
  66. 	MooreDijkstra(&G,1);
  67. 	if(pi[n] == oo) printf("-1 %d", cnt[n]);
  68. 	else printf("%d %d", pi[n], cnt[n]);
  69. }
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 6 6
5 6 9
stdout
copy 
20 1
https://ideone.com/n2JJuB
language:
C (gcc 8.3)
created:
10 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!