比赛 |
20140418 |
评测结果 |
C |
题目名称 |
滑雪场地的难度系数 |
最终得分 |
0 |
用户昵称 |
超级傲娇的AC酱 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2014-04-18 11:26:45 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int M,N;
vector<vector<pair<int,int> > >Map;
int Prim(int,int,int);
int main()
{int T,i,j,A[510][510];
freopen("skilevel.in","r",stdin);
freopen("skilevel.out","w",stdout);
cin>>M>>N>>T;
Map.resize(M*N);
for(i=0;i<M;i++)
for(j=0;j<N;j++)
cin>>A[i][j];
for(i=0;i<M;i++)
for(j=0;j<N;j++)
{
if(i+1<M)Map[i*N+j].push_back(make_pair(abs(A[i+1][j]-A[i][j]),(i+1)*N+j));
if(j+1<M)Map[i*N+j].push_back(make_pair(abs(A[i][j+1]-A[i][j]),(i)*N+j+1));
if(i>0)Map[i*N+j].push_back(make_pair(abs(A[i-1][j]-A[i][j]),(i-1)*N+j));
if(j>0)Map[i*N+j].push_back(make_pair(abs(A[i][j-1]-A[i][j]),(i)*N+j+1));
}
int Ans=0;
for(i=0;i<M;i++)
for(j=0;j<N;j++)
{Ans+=Prim(M*N,i*N+j,T);}
cout<<Ans;
return 0;
}
int Prim(int Len,int pos,int T)
{
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;
bool v[Len];int i;pair<int,int>Node;int Ans=0;
for(i=0;i<Len;i++)
v[i]=false;
Q.push(make_pair(pos,0));
while(!Q.empty())
{
Node=Q.top();
Q.pop();
if(v[Node.second]==false)
{
Ans=min(Ans,Node.first);v[Node.second]=true;
T--;
if(T==0)return Ans;
for(i=0;i<Map[Node.second].size();i++)
if(v[Map[Node.second][i].second]==false)
Q.push(Map[Node.second][i]);
}
}
}
/*
int bfs(int Px,int Py)
{
vector<vector<bool> >B;
deque<pair<int,int> >pos;
int i;
pos.push_back(make_pair(Px,Py));
while(!pos.empty())
{
for(i=0;i<4;i++)
{
posx=pos[i].first+Means[i][0];
posy=pos[i].second+Means[i][0];
if(posx>=0&&posx<M)
if(posx>=0&&posy<N)
if(B[posx][posy]==false)
{
//B[posx][posy]=true;
//pos.push_back(make_pair(posx,posy));////////////////
//T--;
//if(T==0)
//return ans;
}
}
pos.pop_back();
}
}
*/