제출 #1205710

#제출 시각아이디문제언어결과실행 시간메모리
1205710PlayVoltzOlympic Bus (JOI20_ho_t4)C++20
11 / 100
19 ms3656 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); vector<bool> done(n+1, 0); dj[s]=0; for (int ooga=1; ooga<=n; ++ooga){ int node=-1; for (int i=1; i<=n; ++i)if (!done[i]&&(node==-1||dj[i]<dj[node]))node=i; if (node==-1||dj[node]==LLONG_MAX/4)break; done[node]=1; for (auto num:graph[node])dj[num.fi]=min(dj[num.fi], dj[node]+num.se); } 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/4)); 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){ vector<pii> temp; bool done=0; for (auto a:graph[c.fi.fi]){ if (!done&&a==mp(c.fi.se, c.se.fi))done=1; else temp.pb(a); } 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].pop_back(); 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...