제출 #250460

#제출 시각아이디문제언어결과실행 시간메모리
250460combi1k1Olympic Bus (JOI20_ho_t4)C++14
100 / 100
707 ms3256 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld double #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() #define pb emplace_back #define X first #define Y second const int N = 205; const ll inf = 1e18; typedef pair<ll,int> ii; struct Edge { int u, v; int cost; Edge(int _u = 0,int _v = 0,int _c = 0) : u(_u), v(_v), cost(_c) {} }; vector<Edge> E; vector<int> g[N]; bool use[50009]; ll ans[50009]; ll dis[209][209]; int main() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n; cin >> n; int m; cin >> m; for(int i = 1 ; i <= n ; ++i) for(int j = 1 ; j <= n ; ++j) dis[i][j] = (i == j ? 0 : inf); for(int i = 0 ; i < m ; ++i) { int x, y; cin >> x >> y; int c, d; cin >> c >> ans[i]; g[x].pb(i); E.pb(x,y,c); if (dis[x][y] > c) dis[x][y] = c; } for(int k = 1 ; k <= n ; ++k) for(int i = 1 ; i <= n ; ++i) for(int j = 1 ; j <= n ; ++j) dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]); auto FindPath = [&](int S,int T) { vector<ll> d(n + 1,inf); vector<int> p(n + 1,-1); priority_queue<ii,vector<ii>,greater<ii> > pq; pq.push(ii(0,S)); d[S] = 0; while (pq.size()) { int u = pq.top().Y; ll du = pq.top().X; pq.pop(); if (du != d[u]) continue; for(int i : g[u]) { int v = E[i].v; if (d[v] > du + E[i].cost) { d[v] = du + E[i].cost; p[v] = i; pq.push(ii(d[v],v)); } } } if (p[T] < 0) return; while (T != S) { int i = p[T]; use[i] = 1; T = E[i].u; } }; auto dijkstra = [&](int S,int T,int ban) { vector<ll> d(n + 1,inf); priority_queue<ii,vector<ii>,greater<ii> > pq; pq.push(ii(0,S)); d[S] = 0; while (pq.size()) { int u = pq.top().Y; ll du = pq.top().X; pq.pop(); if (du != d[u]) continue; for(int i : g[u]) if (i != ban) { int v = E[i].v; if (d[v] > du + E[i].cost) { d[v] = du + E[i].cost; pq.push(ii(d[v],v)); } } } return d[T]; }; ll Result = dis[1][n] + dis[n][1]; FindPath(1,n); for(int i = 0 ; i < m ; ++i) { if (use[i]) ans[i] += dijkstra(1,n,i); else ans[i] += min(dis[1][n],dis[1][E[i].v] + E[i].cost + dis[E[i].u][n]); use[i] = 0; } FindPath(n,1); for(int i = 0 ; i < m ; ++i) { if (use[i]) ans[i] += dijkstra(n,1,i); else ans[i] += min(dis[n][1],dis[n][E[i].v] + E[i].cost + dis[E[i].u][1]); } for(int i = 0 ; i < m ; ++i) if (Result > ans[i]) Result = ans[i]; if (Result >= 1e18) Result = -1; cout << Result << endl; }

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

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:46:16: warning: unused variable 'd' [-Wunused-variable]
         int c, d;   cin >> c >> ans[i];
                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...