Submission #719972

#TimeUsernameProblemLanguageResultExecution timeMemory
719972yellowtoadCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
332 ms28116 KiB
#include <iostream> #include <vector> #include <queue> #define f first #define se second #define int long long #define pll pair<long long,long long> using namespace std; long long n, m, s, t, ss, tt, dist[100010], disu[100010], disv[100010], vis[100010], in[100010], minu[100010], minv[100010], minn[100010]; vector<pll> edge[100010]; vector<long long> dag[100010]; priority_queue<pll,vector<pll>,greater<pll>> pq; void dijk(int st, long long (&dis)[100010]) { pq.push({0,st}); for (int i = 1; i <= n; i++) dis[i] = 1e18, vis[i] = 0; dis[st] = 0; while (pq.size()) { long long u = pq.top().se; pq.pop(); if (vis[u]) continue; vis[u] = 1; for (int i = 0; i < edge[u].size(); i++) { if (dis[edge[u][i].f] > dis[u]+edge[u][i].se) { dis[edge[u][i].f] = dis[u]+edge[u][i].se; pq.push({dist[edge[u][i].f],edge[u][i].f}); } } } } void dfs(int u) { minu[u] = min(minu[u],disu[u]); minv[u] = min(minv[u],disv[u]); minn[u] = min(minn[u],min(minu[u]+disv[u],minv[u]+disu[u])); for (int i = 0; i < dag[u].size(); i++) { long long v = dag[u][i]; in[v]--; minu[v] = min(minu[v],minu[u]); minv[v] = min(minv[v],minv[u]); minn[v] = min(minn[v],minn[u]); if (!in[v]) dfs(v); } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t >> ss >> tt; for (int i = 1; i <= m; i++) { long long u, v, w; cin >> u >> v >> w; edge[u].push_back({v,w}); edge[v].push_back({u,w}); } dijk(ss,disu); dijk(tt,disv); dijk(s,dist); for (int i = 1; i <= n; i++) { for (int j = 0; j < edge[i].size(); j++) { if (dist[i]+edge[i][j].se == dist[edge[i][j].f]) { dag[i].push_back(edge[i][j].f); in[edge[i][j].f]++; } } } for (int i = 1; i <= n; i++) minu[i] = minv[i] = minn[i] = 1e18; dfs(s); cout << min(disu[tt],minn[t]) << endl; }

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijk(long long int, long long int (&)[100010])':
commuter_pass.cpp:24:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for (int i = 0; i < edge[u].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(long long int)':
commuter_pass.cpp:37:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < dag[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:61:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (int j = 0; j < edge[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...