Submission #773694

#TimeUsernameProblemLanguageResultExecution timeMemory
773694PoonYaPatShortcut (IOI16_shortcut)C++14
0 / 100
2062 ms384 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pii; int n; ll ans=LLONG_MAX; vector<pii> adj[2005]; ll find_shortcut(int N, vector<int> l, vector<int> d, int c) { n=N; for (int i=0; i<n-1; ++i) { adj[i].push_back(pii(i+1,l[i])); adj[i+1].push_back(pii(i,l[i])); } vector<int> v; for (int i=0; i<n; ++i) { v.push_back(i); if (d[i]) { adj[i].push_back(pii(i+500,d[i])); adj[i+500].push_back(pii(i,d[i])); v.push_back(i+500); } } for (int l=0; l<n; ++l) { for (int r=l+1; r<n; ++r) { //consider express in (l,r) adj[l].push_back(pii(r,c)); adj[r].push_back(pii(l,c)); ll mmax=0; for (auto st : v) { priority_queue<pii, vector<pii>, greater<pii>> q; ll dis[1005]; bool vis[1005]; for (int i=0; i<1003; ++i) dis[i]=1e18, vis[i]=false; dis[st]=0; q.push(pii(0,st)); while (!q.empty()) { ll node=q.top().second; q.pop(); mmax=max(mmax,dis[node]); if (vis[node]) continue; vis[node]=true; for (auto s : adj[node]) { if (dis[s.first]>dis[node]+s.second) { dis[s.first]=dis[node]+s.second; q.push(pii(dis[s.first],s.first)); } } } } ans=min(ans,mmax); adj[l].pop_back(); adj[r].pop_back(); } } ll mmax=0; for (auto st : v) { priority_queue<pii, vector<pii>, greater<pii>> q; ll dis[2005]; bool vis[2005]; for (int i=0; i<2003; ++i) dis[i]=1e18, vis[i]=false; dis[st]=0; q.push(pii(0,st)); while (!q.empty()) { ll node=q.top().second; q.pop(); mmax=max(mmax,dis[node]); if (vis[node]) continue; vis[node]=true; for (auto s : adj[node]) { if (dis[s.first]>dis[node]+s.second) { dis[s.first]=dis[node]+s.second; q.push(pii(dis[s.first],s.first)); } } } } ans=min(ans,mmax); return 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...