Submission #64942

#TimeUsernameProblemLanguageResultExecution timeMemory
64942gs18115물탱크 (KOI18_watertank)C++14
0 / 100
170 ms16024 KiB
#include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; typedef long long LL; const LL INF=1e18; const LL SC=1002; const LL MAXN=1005; pair<pair<LL,LL>,LL>adj[MAXN][MAXN][5]; LL adjN[MAXN][MAXN]; LL dist[MAXN][MAXN]; bool inQ[MAXN][MAXN]; LL N,M,i,j,H,a,s; void makeedge(LL i1,LL j1,LL i2,LL j2,LL w) { adj[i1][j1][adjN[i1][j1]++]=make_pair(make_pair(i2,j2),w); adj[i2][j2][adjN[i2][j2]++]=make_pair(make_pair(i1,j1),w); return; } void spfa() { queue<pair<LL,LL> >Q; LL i; for(i=0;i<MAXN;i++) fill(dist[i],dist[i]+MAXN,INF); for(i=0;i<MAXN;i++) fill(inQ[i],inQ[i]+MAXN,false); dist[SC][SC]=0; Q.push(make_pair(SC,SC)); while(!Q.empty()) { LL hi=Q.front().first; LL hj=Q.front().second; Q.pop(); inQ[hi][hj]=false; for(i=0;i<adjN[hi][hj];i++) { LL ti=adj[hi][hj][i].first.first; LL tj=adj[hi][hj][i].first.second; LL wei=adj[hi][hj][i].second; if(dist[ti][tj]>max(wei,dist[hi][hj])) { dist[ti][tj]=max(wei,dist[hi][hj]); if(!inQ[ti][tj]) { inQ[ti][tj]=true; Q.push(make_pair(ti,tj)); } } } } return; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>N>>M>>H; for(i=0;i<=N;i++) { for(j=0;j<M;j++) { cin>>a; if(a==-1) continue; else if(i==0) makeedge(i,j,SC,SC,a); else if(i==N) makeedge(i-1,j,SC,SC,a); else makeedge(i,j,i-1,j,a); } } for(i=0;i<N;i++) { for(j=0;j<=M;j++) { cin>>a; if(a==-1) continue; else if(j==0) makeedge(i,j,SC,SC,a); else if(j==M) makeedge(i,j-1,SC,SC,a); else makeedge(i,j,i,j-1,a); } } spfa(); for(i=0;i<N;i++) for(j=0;j<M;j++) s+=dist[i][j]; cout<<s<<endl; return 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...
#Verdict Execution timeMemoryGrader output
Fetching results...