제출 #1205694

#제출 시각아이디문제언어결과실행 시간메모리
1205694PlayVoltzOlympic Bus (JOI20_ho_t4)C++20
5 / 100
1095 ms5416 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> #include <cassert> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second int n; vector<vector<pii> > graph; int dijk(int s, int e){ vector<int> dj(n+1, LLONG_MAX/4); priority_queue<pii, vector<pii>, greater<pii> > pq; pq.push(mp(0, s)); while (pq.size()){ int d=pq.top().fi, node=pq.top().se; pq.pop(); if (d>=dj[node])continue; dj[node]=d; for (auto num:graph[node])pq.push(mp(d+num.se, num.fi)); } return dj[e]; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m, ans=LLONG_MAX/4; cin>>n>>m; graph.resize(n+1); vector<pair<pii, pii> > edges(m); vector<vector<int> > dist(n+1, vector<int>(n+1, LLONG_MAX/2)); for (int i=1; i<=n; ++i)dist[i][i]=0; for (int i=0, a, b, c, d; i<m; ++i){ cin>>a>>b>>c>>d; edges[i]=mp(mp(a, b), mp(c, d)); graph[a].pb(mp(b, c)); dist[a][b]=min(dist[a][b], c); } for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)for (int p=1; p<=n; ++p)dist[j][p]=min(dist[j][p], dist[j][i]+dist[i][p]); ans=min(ans, dijk(1, n)+dijk(n, 1)); for (auto c:edges)if (c.se.se+min(dist[1][n], dist[1][c.fi.se]+dist[c.fi.fi][n]+c.se.fi)+min(dist[n][1], dist[n][c.fi.se]+dist[c.fi.fi][1]+c.se.fi)<ans){ graph[c.fi.fi].erase(remove(graph[c.fi.fi].begin(), graph[c.fi.fi].end(), mp(c.fi.se, c.se.fi))); graph[c.fi.se].pb(mp(c.fi.fi, c.se.fi)); ans=min(ans, dijk(1, n)+dijk(n, 1)+c.se.se); graph[c.fi.se].erase(remove(graph[c.fi.se].begin(), graph[c.fi.se].end(), mp(c.fi.fi, c.se.fi))); graph[c.fi.fi].pb(mp(c.fi.se, c.se.fi)); } cout<<(ans==LLONG_MAX/4?-1:ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...