Submission #949930

#TimeUsernameProblemLanguageResultExecution timeMemory
949930sondos225Relay Marathon (NOI20_relaymarathon)C++17
0 / 100
558 ms1048576 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template<typename T>using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;//find_by_order(ind); //order_of_key() #define int long long #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); #define pb push_back #define yes "YES" #define no "NO" #define bigg INT_MAX #define debug(x) cout<<(#x)<<" = " <<x<<endl; #define all(x) x.begin(),x.end() #define sz size() #define nn '\n' #define mms(x,y) memset(x,y,sizeof(x)) #define forr(i,j,n) for (int i=j; i<n; i++) #define forn(i,j,n) for (int i=j; i>n; i--) #define fi first #define se second #define la "LA" #define cinn(x,y) for(int i=0; i<y; i++) cin>>x[i]; #define pii pair<int,int> signed main() { // #ifndef LOCAL // freopen("lifeguards.in","r",stdin); // freopen("lifeguards.out","w", stdout); // #endif fast int n,m,k; cin>>n >>m >>k; int dis[n+1][n+1]; forr(i,1,n+1) { forr(j,1,n+1) { if (i==j) dis[i][j]=0; else dis[i][j]=bigg; } } forr(i,0,m) { int x,y,z; cin>>x >>y >>z; // a[x].pb({y,z}); // a[y].pb({x,z}); dis[x][y]=z; dis[y][x]=z; } int s[k]; bool b[n+1]= { }; forr(i,0,k) { cin>>s[i]; b[s[i]]=1; } vector<pii> top3[n+1]; forr(i,1,n+1) { vector<pii> cur; forr(j,1,n+1) { if (i==j) continue; forr(k,1,n+1) { dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } if (b[i] && b[j]) cur.pb({dis[i][j],j});//cout<<la<<i<<' '<<j<<' '<<dis[i][j]<<endl; } sort(all(cur)); if(cur.sz>0) top3[i].pb(cur[0]); if(cur.sz>1) top3[i].pb(cur[1]); if(cur.sz>2) top3[i].pb(cur[2]); } int ans=bigg; forr(i,0,k) { int x=s[i]; if (top3[x].sz==0) continue; forr(j,0,k) { if (i==j) continue; int y=s[j]; int cur=top3[x][0].fi; int nope=top3[x][0].se; if (y==nope) continue; if (top3[y].sz==0) continue; if (top3[y][0].se!=nope && top3[y][0].se!=x) cur+=top3[y][0].fi; else if (top3[y].sz==1) continue; else if (top3[y][1].se!=nope && top3[y][1].se!=x) cur+=top3[y][1].fi; else if (top3[y].sz==2) continue; else if (top3[y][2].se!=nope && top3[y][2].se!=x) cur+=top3[y][2].fi; else if (top3[y].sz==3) continue; else cur+=top3[y][3].fi; // cout<<x<<' '<<y<<' '<<cur<<endl; ans=min(ans,cur); } } if (ans==bigg) ans/=0; cout<<ans; return 0; }

Compilation message (stderr)

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:102:23: warning: division by zero [-Wdiv-by-zero]
  102 |     if (ans==bigg) ans/=0;
      |                    ~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...