小咕儿做P1828
voyage1969 · · 题解
图中所有边权均为正数，不存在负权环，那么可以使用使用 DIJKSTRA 算法解决。
DIJKSTRA算法的步骤和原理：
0.申请一个包含点和点权（距离）的结构体的优先队列，按照点权非降序排序。
1.将一个点（源点）加入优先队列。点权为0。
2.当优先队列不为空时，执行以下操作：
2.1. 取出优先队列对顶的元素。
2.2. 如果这个元素对应的点第一次从队列中取出，那么将这个点的最短距离修改为这个元素对应的点权。
2.3. 枚举这个点能直接连通且未从队列中取出的新点，如果通过该点到达新点的距离小于原来到达新点的距离，则将新点的距离更新，并将新点和新点的点权组成的元素压入优先队列。
3.得解，返回。
原理很明显。如果我们在图中源点周围的边寻找一条最短的边，那么源点到该边另一端的点的距离不可能比这条边的长度短。相应的，按此方法在已经求得可能是最优路径的点中，路径最短的那一点一定是在经过了最短路的，不可能从其他地方找到一条更短的路径。因此 DIJKSTRA 总能找到无负权环的图中从一个点出发到其他点的最短距离。
思路
枚举奶牛们吃糖的牧场i(1~p)，让奶牛们都走最优路径赶到此处。则以当前节点为源头进行一次 DIJKSTRA 算法，在计算出点i和点j(1~p)的最优路径，同时统计点j的奶牛走到点i的总路程。
代码
见下。（利用了一些OO特性。）
#include<cstdio>
#include<queue>
////////////////////////////////////////////////////////////////
const int N=505,P=805,C=1455;
////////////////////////////////////////////////////////////////
class typeEdge;
class typeNode;
////////////////////////////////////////////////////////////////
class typeEdge
{
private:
int _len;
typeNode * _ob;
typeEdge * _pre;
public:
int len() { return this->_len; }
typeNode * ob() { return this->_ob; }
typeEdge * pre() { return this->_pre; }
void fill(typeNode *,typeNode *,int); //done
void back(); //done
bool bottom(); //done
};
class typeNode
{
private:
struct type1;
struct type1
{
int i1;
typeNode * no1;
friend bool operator < (type1 left,type1 right)
{
return left.i1>right.i1;
}
};
char _state;
int _power;
int _dist;
typeEdge * _last;
public:
char state() { return this->_state; }
int power() { return _power; }
int dist() { return _dist; }
typeEdge * last() { return _last; }
void fill(int); //done
void reset(); //done
int dijkstra(); //done
bool updateDist(int); //done
void updateLast(typeEdge *); //done
};
////////////////////////////////////////////////////////////////
int n,p,c,t,a,b,d,ans;
typeNode node[P];
typeEdge edge[2*C+P];
////////////////////////////////////////////////////////////////
int main()
{
scanf("%d%d%d",&n,&p,&c);
for(int i=0;i<n;i++)
{
scanf("%d",&t);
node[t].fill(node[t].power()+1);
}
for(int i=1;i<=p;i++)
{
edge[2*c+i].fill(node+i,node,0x33333333);
}
for(int i=0;i<c;i++)
{
scanf("%d%d%d",&a,&b,&d);
edge[2*i].fill(node+a,node+b,d);
edge[2*i+1].fill(node+b,node+a,d);
}
ans=0x33333333;
for(int i=1;i<=p;i++)
{
for(int j=1;j<=p;j++) node[j].reset();
ans=std::min(ans,node[i].dijkstra());
}
printf("%d\n",ans);
return 0;
}
////////////////////////////////////////////////////////////////
void typeNode::fill(int pa1)
{
this->_power=pa1;
return;
}
void typeNode::reset()
{
this->_dist=0x77777777;
this->_state='V'; //virgin.
return;
}
bool typeNode::updateDist(int pa1)
{
if(this->dist()>pa1)
{
this->_dist=pa1;
return 1;
}
else return 0;
}
void typeNode::updateLast(typeEdge * pa1)
{
this->_last=pa1;
return;
}
int typeNode::dijkstra()
{
int totdist;
std::priority_queue<type1>uPQ;
this->_dist=0;
type1 u1;
u1=(type1){ this->dist(),this };
uPQ.push(u1),u1.no1->_state='I'; //in queue.
totdist=0;
while(!uPQ.empty())
{
type1 u2;
u2=uPQ.top(),uPQ.pop();
if(u2.no1->state()=='U') continue;
u2.no1->_state='U'; //used.
totdist+=u2.no1->power()*u2.no1->dist();
for(typeEdge ed1=*u2.no1->last();!ed1.bottom();ed1.back())
{
typeNode * no2;
no2=ed1.ob();
if(no2->updateDist(u2.i1+ed1.len()))
{
u1=(type1){ no2->dist(),no2 };
uPQ.push(u1),u1.no1->_state='I'; //in queue.
}
}
}
return totdist;
}
////////////////////////////////////////////////////////////////
void typeEdge::fill(typeNode * pa1,typeNode * pa2,int pa3)
{
this->_pre=pa1->last();
this->_ob=pa2;
this->_len=pa3;
pa1->updateLast(this);
return;
}
void typeEdge::back()
{
*this=*(this->pre());
return;
}
bool typeEdge::bottom()
{
if(this->pre()==NULL) return 1;
else return 0;
}
////////////////////////////////////////////////////////////////
（DIJKSTRA是一种用一个最小堆维护的计算图中单源最短路径算法。主要利用了贪心和动态规划的思想，时间复杂度较为优异。）