Advertisement
Guest User

Untitled

a guest
Dec 9th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.88 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. import java.util.StringTokenizer;
  5.  
  6. public class Main {
  7.  
  8. public static int min(Long[] path, boolean[] visit) {
  9. Long priceWay = Long.MAX_VALUE;
  10. int position = 0;
  11. for (int i = 1; i < path.length; i++) { // 0 -> 1
  12. if (!visit[i] && path[i] <= priceWay) {
  13. priceWay = path[i];
  14. position = i;
  15. }
  16. }
  17. return position;
  18. }
  19.  
  20. public static void main(String[] args) throws Exception {
  21. BufferedReader br = new BufferedReader(new FileReader(new File("input.txt")));
  22. PrintWriter pr = new PrintWriter(new File("output.txt"));
  23. StringTokenizer st = new StringTokenizer(br.readLine());
  24. int N = Integer.parseInt(st.nextToken());
  25. int M = Integer.parseInt(st.nextToken());
  26. Top tops[] = new Top[N + 1];
  27. for(int i = 1;i <= N;i++){
  28. tops[i] = new Top();
  29. }
  30. int weight;
  31. int n;
  32. int m;
  33. for (int i = 1; i <= M; i++) {
  34. st = new StringTokenizer(br.readLine());
  35. n = Integer.parseInt(st.nextToken());
  36. m = Integer.parseInt(st.nextToken());
  37. weight = Integer.parseInt(st.nextToken());
  38. tops[n].addTop(m, weight);
  39. tops[m].addTop(n, weight);
  40. }
  41. st = new StringTokenizer(br.readLine());
  42. int start = Integer.parseInt(st.nextToken());
  43. int finish = Integer.parseInt(st.nextToken());
  44. int q = Integer.parseInt(st.nextToken());
  45. Long[] path = new Long[N+1];
  46. boolean[] visit = new boolean[N+1];
  47. for (int i = 1; i <= N; i++) {
  48. path[i] = Long.MAX_VALUE;
  49. }
  50. path[start] = (long) q * tops[start].numberRoad.size();
  51. for (int i = 0; i < N; i++) {
  52. visit[start] = true;
  53. for (int j = 0; j < tops[start].numberRoad.size(); j++) {
  54. m = tops[start].numberRoad.get(j);
  55. if (!visit[m] && path[m] > (path[start] + tops[start].weight.get(j) + q * tops[m].numberRoad.size())) {
  56. path[m] = path[start] + tops[start].weight.get(j) + q * tops[m].numberRoad.size();
  57. }
  58. }
  59. start = min(path, visit);
  60. }
  61. long answer = path[finish] - q * tops[finish].numberRoad.size();
  62. if (path[finish] != Long.MAX_VALUE) {
  63. pr.println("Yes");
  64. pr.print(answer);
  65. } else {
  66. pr.print("No");
  67. }
  68. pr.close();
  69. }
  70. }
  71.  
  72. class Top {
  73. public List<Integer> numberRoad;
  74. public List<Integer> weight;
  75.  
  76. public Top() {
  77. numberRoad = new ArrayList<>();
  78. weight = new ArrayList<>();
  79. }
  80.  
  81. public void addTop(int point, int tempWeight) {
  82. numberRoad.add(point);
  83. weight.add(tempWeight);
  84. }
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement