fork(1) download
  1. #include <cstdio>
  2.  
  3. const int INF = 10000000;
  4.  
  5. int N, M;
  6. int S, E;
  7.  
  8. int data[203][203];
  9.  
  10. int main() {
  11. scanf("%d %d", &N, &M);
  12.  
  13. for (int i = 1; i <= N; i ++) {
  14. for (int j = 1; j <= N; j ++) {
  15. data[i][j] = INF;
  16. }
  17. data[i][i] = 0;
  18. }
  19.  
  20. while (M --) {
  21. int a, b, c;
  22. scanf("%d %d %d", &a, &b, &c);
  23. if (data[a][b] > c) {
  24. data[a][b] = c;
  25. }
  26. }
  27.  
  28. scanf("%d %d", &S, &E);
  29.  
  30. for (int k = 1; k <= N; k ++) {
  31. for (int i = 1; i <= N; i ++) {
  32. for (int j = 1; j <= N; j ++) {
  33. if (data[i][j] > data[i][k] + data[k][j]) {
  34. data[i][j] = data[i][k] + data[k][j];
  35. }
  36. }
  37. }
  38. }
  39.  
  40. int cnt = 0;
  41. for (int i = 1; i <= N; i ++) {
  42. if (data[S][i] + data[i][E] == data[S][E]) {
  43. cnt ++;
  44. }
  45. }
  46.  
  47. printf("%d\n", cnt);
  48. for (int i = 1; i <= N; i ++) {
  49. if (data[S][i] + data[i][E] == data[S][E]) {
  50. printf("%d\n", i);
  51. }
  52. }
  53. return 0;
  54. }
Success #stdin #stdout 0s 3632KB
stdin
4 4
1 3 1
3 4 1
1 2 1
2 4 1
1 4
stdout
4
1
2
3
4