SHARE
TWEET

Untitled

a guest Feb 19th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "pch.h"
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. int n, m = 0;
  8. long long dp[10001][2];
  9. bool used[10000];
  10. vector <vector<long long>> cost;
  11. vector <vector<int>> edge;
  12. vector <vector<int>> type;
  13.  
  14. int main()
  15. {
  16.  
  17.     cin >> n >> m;
  18.     cost.resize(n);
  19.     edge.resize(n);
  20.     type.resize(n);
  21.     for (int i = 0; i < m; i++) {
  22.         string str;
  23.         int tpn, tptw, cst;
  24.         cin >> tpn >> tptw >> cst >> str;
  25.         if (str[0] == 'L') {
  26.             type[tptw - 1].push_back(0);
  27.         }
  28.         if (str[0] == 'P') {
  29.             type[tptw - 1].push_back(1);
  30.         }
  31.         if (str[0] == 'C') {
  32.             type[tptw - 1].push_back(2);
  33.         }
  34.         edge[tptw - 1].push_back(tpn - 1);
  35.         cost[tptw - 1].push_back(cst);
  36.     }
  37.     cout << 1;
  38.     used[0] = true;
  39.     for (int i = 0; i < n; i++) {
  40.         used[i + 1] = false;
  41.         for (int k = 0; k < edge[i].size(); k++) {
  42.             if (used[edge[i][k]] == true && (type[i][k] == 0 || type[i][k] == 2)) {
  43.                 used[i] = true;
  44.             }
  45.         }
  46.         long long min = 100000000000ll;
  47.         for (int k = 0; k < edge[i].size(); k++) {
  48.             if (used[edge[i][k]] == true && used[i] == true) {
  49.                 if (min > dp[edge[i][k]][0] + cost[i][k]) {
  50.                     min = dp[edge[i][k]][0] + cost[i][k];
  51.                 }
  52.             }
  53.         }
  54.         dp[i][0] = min;
  55.         if (dp[i][0] == 100000000000ll) {
  56.             dp[i][0] = 0;
  57.         }
  58.     }
  59.  
  60.     used[0] = true;
  61.     for (int i = 0; i < n; i++) {
  62.         used[i + 1] = false;
  63.         for (int k = 0; k < edge[i].size(); k++) {
  64.             if (used[edge[i][k]] == true) {
  65.                 used[i] = true;
  66.             }
  67.         }
  68.         long long min = 100000000000ll;
  69.         for (int k = 0; k < edge[i].size(); k++) {
  70.             if (used[edge[i][k]] == true && used[i] == true) {
  71.                 if (min > dp[edge[i][k]][0] + cost[i][k]) {
  72.                     min = dp[edge[i][k]][0] + cost[i][k];
  73.                 }
  74.                 if ((min > dp[edge[i][k]][1] + cost[i][k]) && (type[i][k] == 1 || type[i][k] == 2) ) {
  75.                     min = dp[edge[i][k]][1] + cost[i][k];
  76.                 }
  77.             }
  78.         }
  79.         dp[i][1] = min;
  80.         if (dp[i][0] == 100000000000ll) {
  81.             dp[i][0] = 0;
  82.         }
  83.     }
  84.     if (dp[n - 1][0] > dp[n - 1][1]) {
  85.         long long answer = dp[n - 1][1];
  86.     }
  87.     else {
  88.         long long answer = dp[n - 1][0];
  89.     }
  90.     cout << 1;
  91.     if(dp[n-1][0] == dp[n-1][1] && dp[n-1][0] == 0){
  92.         cout << 'Offline';
  93.     else{
  94.         cout << 'Online' << endl;
  95.         cout << answer;
  96. }
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