Submission #605270

#	Time	Username	Problem	Language	Result	Execution time	Memory
605270		jjiangly	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	50 ms	2004 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define siz(x) int(x.size())
#define ll long long
#define ar array
#define vt vector
#define inf int(1e9)
#define lnf (long long) 1e12

const int nxm = int(3e2) + 7;
int n, m, t, s, u, v;
ll e[nxm][nxm];

namespace sub3 {
  void exe() {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        e[i][j] = lnf;
      }
    }
    for (int i = 0; i < n; ++i) {
      e[i][i] = 0;
    }
    for (int i = 0; i < m; ++i) {
      int a, b;
      cin >> a >> b;
      --a, --b;
      cin >> e[a][b];
      e[b][a] = e[a][b];
    }
    for (int k = 0; k < n; ++k) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          if (e[i][k] != lnf && e[k][j] != lnf) {
            e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
          }
        }
      }
    }
    ll ans = e[u][v];
    //cout << e[4][0] + e[0][1] + e[1][6] << " " << e[4][6] << " " << e[5][1] << " " << e[0][7] << "\n";
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (e[t][i] + e[i][j] + e[j][s] == e[t][s]) {
          ans = min(ans, e[u][i] + e[j][v]);
          ans = min(ans, e[u][j] + e[i][v]);
        }
      }
    }
    cout << ans << "\n";
  }
};

int subtask() {
  if (n <= 300) {
    return 3;
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> t >> s >> u >> v;
  --t, --s, --u, --v;
  if (subtask() == 3) {
    sub3::exe();
  }

  return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int subtask()':
commuter_pass.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45