Submission #851614

#TimeUsernameProblemLanguageResultExecution timeMemory
851614nhamtandeptraiCommuter Pass (JOI18_commuter_pass)C++17
31 / 100
246 ms18488 KiB
#include<bits/stdc++.h> using namespace std; #define y1 as214 #define ii pair < int , int > #define iii pair < int , ii > #define iv pair < ii , ii > #define fi first #define se second #define fr front() #define pb push_back #define FOR(i , x , n) for(int i = x ; i <= n ; ++i) #define REP(i , n) for(int i = 0 ; i < n ; ++i) #define FORD(i , x , n) for(int i = x ; i >= n ; --i) #define ll long long #define oo 1e9 #define eps 1e-8 #define div divv #define pow poww #define int long long const int N = 1e5 + 5; int n , m , u , v , s , t; int distu[N] , distv[N] , dists[N] , distt[N]; vector < ii > g[N]; priority_queue < ii , vector < ii > , greater < ii > > q; void dijk(int start , int dist[]) { FOR(i , 1 , n) dist[i] = 1e18; dist[start] = 0; q.push(ii(dist[start] , start)); while(!q.empty()) { int u = q.top().se; int cost = q.top().fi; q.pop(); if(cost > dist[u]) continue; REP(s , g[u].size()) { int v = g[u][s].fi; int w = g[u][s].se; if(dist[v] > dist[u] + w) q.push(ii(dist[v] = dist[u] + w , v)); } } } main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; cin >> s >> t; cin >> u >> v; FOR(i , 1 , m) { int u , v , w; cin >> u >> v >> w; g[u].pb(ii(v , w)); g[v].pb(ii(u , w)); } dijk(s , dists); dijk(t , distt); dijk(u , distu); dijk(v , distv); int ans1 = 1e18; int ans2 = 1e18; FOR(i , 1 , n) if(dists[i] != 1e18 && distt[i] != 1e18 && dists[i] + distt[i] == dists[t]) { if(distu[i] != 1e18) ans1 = min(ans1 , distu[i]); if(distv[i] != 1e18) ans2 = min(ans2 , distv[i]); //cout << i << endl; } if(distu[v] != 1e18) cout << min(ans1 + ans2 , distu[v]) << "\n"; else cout << ans1 + ans2; }

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijk(long long int, long long int*)':
commuter_pass.cpp:15:38: 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]
   15 | #define REP(i , n) for(int i = 0 ; i < n ; ++i)
......
   44 |         REP(s , g[u].size())
      |             ~~~~~~~~~~~~~~~           
commuter_pass.cpp:44:9: note: in expansion of macro 'REP'
   44 |         REP(s , g[u].size())
      |         ^~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...