daily pastebin goal
29%
SHARE
TWEET

Untitled

a guest Jul 13th, 2018 62 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. OK, I Understand
 
Top