Submission #64969

#TimeUsernameProblemLanguageResultExecution timeMemory
64969gs18115물탱크 (KOI18_watertank)C++14
100 / 100
1681 ms204840 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; vector<pair<pair<LL,LL>,LL> >adj[MAXN][MAXN]; LL adjN[MAXN][MAXN]; LL dist[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].push_back(make_pair(make_pair(i2,j2),w)); adj[i2][j2].push_back(make_pair(make_pair(i1,j1),w)); return; } void path() { priority_queue<pair<LL,pair<LL,LL> >,vector<pair<LL,pair<LL,LL> > >,greater<pair<LL,pair<LL,LL> > > >PQ; LL i; for(i=0;i<MAXN;i++) fill(dist[i],dist[i]+MAXN,INF); PQ.push(make_pair(0,make_pair(SC,SC))); while(!PQ.empty()) { LL hi=PQ.top().second.first; LL hj=PQ.top().second.second; LL dis=PQ.top().first; PQ.pop(); if(dist[hi][hj]!=INF) continue; dist[hi][hj]=dis; for(i=0;i<adj[hi][hj].size();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]==INF) PQ.push(make_pair(max(wei,dist[hi][hj]),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); } } path(); for(i=0;i<N;i++) for(j=0;j<M;j++) s+=(dist[i][j]==INF?H:dist[i][j]); cout<<s<<endl; return 0; }

Compilation message (stderr)

watertank.cpp: In function 'void path()':
watertank.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<adj[hi][hj].size();i++)
                 ~^~~~~~~~~~~~~~~~~~~
#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...