• API
• FAQ
• Tools
• Archive
daily pastebin goal
57%
SHARE
TWEET

# Untitled

a guest Jul 13th, 2018 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <cstdio>
2. #include <algorithm>
3. #include <iostream>
4. #include <string>
5. #include <vector>
6. #include <map>
7. #define INF 987654321
8. using namespace std;
9. int n, r, x, y;
10. string a, b, c;
11. map<string, int> mp;
12. vector<int> trip;
13. int arr[110][110];
14. int brr[110][110];
15. void init() {
16.     for (int i = 1; i <= n; i++) {
17.         for (int j = 1; j <= n; j++) {
18.             if (i == j)arr[i][j] = brr[i][j] = 0;
19.             else arr[i][j] = brr[i][j] = INF;
20.         }
21.     }
22. }
23. void fw() {
24.     for (int k = 1; k <= n; k++) {
25.         for (int i = 1; i <= n; i++) {
26.             for (int j = 1; j <= n; j++) {
27.                 if (arr[i][k] + arr[k][j] < arr[i][j])
28.                     arr[i][j] = arr[i][k] + arr[k][j];
29.                 if (brr[i][k] + brr[k][j] < brr[i][j])
30.                     brr[i][j] = brr[i][k] + brr[k][j];
31.             }
32.         }
33.     }
34. }
35. bool sol() {
36.     int ac = 0, bc = 0;
37.     for (int i = 0; i < trip.size() - 1; i++) {
38.         ac += arr[trip[i]][trip[i + 1]];
39.         bc += brr[trip[i]][trip[i + 1]];
40.     }
41.     return bc + r < ac;
42. }
43. int main()
44. {
45.     scanf("%d%d", &n, &r);
46.     init();
47.     for (int i = 1; i <= n; i++) {
48.         cin >> a;
49.         mp[a] = i;
50.     }
51.     scanf("%d", &x);
52.     for (int i = 0; i < x; i++) {
53.         cin >> a;
54.         trip.push_back(mp[a]);
55.     }
56.     scanf("%d", &x);
57.     for (int i = 0; i < x; i++) {
58.         cin >> a >> b >> c;
59.         scanf("%d", &y);
60.         arr[mp[b]][mp[c]] = min(y, arr[mp[b]][mp[c]]);
61.         arr[mp[c]][mp[b]] = min(y, arr[mp[b]][mp[c]]);
62.         if (a == "S-Train" || a == "V-Train") {
63.             brr[mp[b]][mp[c]] = min(y / 2, brr[mp[b]][mp[c]]);
64.             brr[mp[c]][mp[b]] = min(y / 2, brr[mp[b]][mp[c]]);
65.         }
66.         else if(a=="Mugunghwa"||a=="ITX-Saemaeul"||a=="ITX-Cheongchun") {
67.             brr[mp[b]][mp[c]] = 0;
68.             brr[mp[c]][mp[b]] = 0;
69.         }
70.         else {
71.             brr[mp[b]][mp[c]] = min(y, brr[mp[b]][mp[c]]);
72.             brr[mp[c]][mp[b]] = min(y, brr[mp[b]][mp[c]]);
73.         }
74.     }
75.     fw();
76.     printf("%s\n", sol() ? "Yes" : "No");
77.     return 0;
78. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top