제출 #754393

#제출 시각아이디문제언어결과실행 시간메모리
754393penguin133Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
393 ms27232 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int dist1[300005], dist2[300005], n, m, s, t, u, v; vector <pi> adj[100005]; int brr[100005][4]; void dijk(int dist[], int ss){ for(int i = 1; i <= n; i++)dist[i] = 1e18; dist[ss] = 0; priority_queue <pi, vector <pi>, greater<pi> > pq; pq.push({0, ss}); while(!pq.empty()){ int x = pq.top().fi, y = pq.top().se; pq.pop(); if(dist[y] < x)continue; for(auto [i, j] : adj[y]){ if(dist[i] > x + j)dist[i] = x + j, pq.push({dist[i], i}); } } } void solve(){ cin >> n >> m >> s >> t >> u >> v; while (m--){ int a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } dijk(dist1, s); dijk(dist2, t); for(int i = 1; i <= n; i++)for(int j = 0; j < 4; j++)brr[i][j] = 1e18; brr[u][0] = brr[u][1] = brr[u][2] = brr[u][3] = 0; priority_queue <pii, vector<pii>, greater<pii> > pq; pq.push({0, {u, 0}}); while(!pq.empty()){ int x = pq.top().fi, y = pq.top().se.fi, z = pq.top().se.se; pq.pop(); if(brr[y][z] < x)continue; for(auto [i, j] : adj[y]){ if(z == 0){ if(dist1[y] + dist2[i] + j == dist1[t]){ if(brr[i][1] > x)brr[i][1] = x, pq.push({brr[i][1], {i, 1}}); } else if(dist1[i] + dist2[y] + j == dist1[t]){ if(brr[i][2] > x)brr[i][2] = x, pq.push({brr[i][2], {i, 2}}); } if(brr[i][0] > x + j)brr[i][0] = x + j, pq.push({brr[i][0], {i, 0}}); } else if(z == 1){ if(dist1[y] + j + dist2[i] == dist1[t]){ if(brr[i][1] > x)brr[i][1] = x, pq.push({brr[i][1], {i, 1}}); } else{ if(brr[i][3] > x + j)brr[i][3] = x + j, pq.push({brr[i][3], {i, 3}}); } } else if(z == 2){ if(dist1[i] + dist2[y] + j == dist1[t]){ if(brr[i][2] > x)brr[i][2] = x, pq.push({brr[i][2], {i, 2}}); } else{ if(brr[i][3] > x + j)pq.push({x + j, {i, 3}}), brr[i][3] = x + j; } } else{ if(brr[i][3] > x + j)brr[i][3] = x + j, pq.push({brr[i][3], {i, 3}}); } } } cout << min({brr[v][0], brr[v][1], brr[v][2], brr[v][3]}); } main(){ ios::sync_with_stdio(0);cin.tie(0); int tc = 1; //cin >> tc; for(int tc1=1;tc1<=tc;tc1++){ // cout << "Case #" << tc1 << ": "; solve(); } }

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | 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...