[Usaco2004 Nov]Til the Cows Come Home 带奶牛回家（Dijkstra的优化）
Menu
Problem
Time Limit: 1 Sec Memory Limit: 128 MB
Description
贝茜在谷仓外的农场上，她想回到谷仓，在第二天早晨农夫约翰叫她起来挤奶之前尽可能多地睡上一觉．由于需要睡个好觉，贝茜必须尽快回到谷仓．农夫约翰的农场上有N(2≤N≤1000)个路标，每一个路标都有唯一的编号（1到N）．路标1是谷仓，路标N是贝茜一整天呆在那里的果树园．农场的所有路标之间共有T(1≤T≤2000)条不同长度的供奶牛走的有无向小路．贝茜对她识别方向的能力不是很自信，所以她每次总是从一条小路的头走到尾，再以这条路的尾作为下一条路的头开始走． 现给出所有路标之间的小路，要求输出贝茜回到谷仓的最短路程（每组输入数据都保证有解）．
Input
第1行：2个整数T和N．
第2到T+1行：每行用空格隔开的三个整数描述一条小路．前两个整数是这条小路的尾和头，
第三个整数是这条小路的长度（不大于100）．
Output
一个整数，表示贝茜从路标N到路标1所经过的最短路程
Sample Input
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output
90
HINT
共有5个路标，贝茜可以依次经过路标4，3，2，1到家。
1.题目分析
此题明显最短路，是求1 to n的最短路。
这里我们选择Dijkstra算法来求最短路。
这里强调一下，Dijkstra算法的核心就是贪心，这也正是为什么它不能处理负边权的原因。
[PS：注意是无向路]
2.Dijkstra算法的逆袭
①朴素的Dijkstra&卡数据
直接朴素的算法走一波，但要注意一点，其实也不能说注意，主要是数据的问题，
或者说邻接表的局限，所以这里我们要特殊处理一下[#滑稽]。
未优化Dijkstra Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#pragma GCC optimize(2)
#define ri register int //放寄存器里，卡常数
#define N 1001
using namespace std;
int t,n;
bool vis[N];
int dis[N],g[N][N];
void Dijkstra()
{
for (ri i=1;i<=n;++i) dis[i]=g[1][i]; //dis初始化
dis[1]=0,vis[1]=true; //标记
int min,u; //u表示当前找到的最短边所连接的未被访问点
for (ri i=1;i<n;++i)
{
min=0x3f3f3f3f,u=0; //min,u初始化
for (ri p=1;p<=n;++p)
if (!vis[p]&&min>dis[p]) u=p,min=dis[p];
//如果当前找的点未被访问且比上次找的最短路小，更新
if (!u) break; //如果未被更新，则说明都已求出最短路，退出
vis[u]=true; //标记当前找的点为true
for (ri v=1;v<=n;++v)
if (u!=v&&dis[v]>dis[u]+g[u][v])//找到点不与其重合且小于目前所找的最短距离
dis[v]=dis[u]+g[u][v]; //更新
}
}
int main()
{
memset(g,0x7f,sizeof(g)); //g初始化
scanf("%d%d",&t,&n);
for (ri u,v,w,i=1;i<=t;++i)
{
scanf("%d%d%d",&u,&v,&w);
g[u][v]=g[v][u]=min(w,g[u][v]);
//好了这里就是关键中的关键[划去]
//由于数据里出现奇葩的都是描述一组边的，
//而答案偏偏是这些同一条边中权值最小的，所以用min...，不然输出最后一组边的长
}
Dijkstra();
printf("%d",dis[n]);
return 0;
}
好了，这就是我们经过数据洗礼的Dijkstra算法的代码，但这是因为本蒟蒻偷看了数据才知道的问题，比赛有时也像这么坑，那么我们应该怎样用一种新东西来替代邻接表呢？所以，这里要引进一种高级的链式前向星！！！
小插曲：链式前向星
这个名字确实很屌，但它实际上就是邻接表的静态实现。——转自链式前向星实现以及它的遍历，Kirai大佬的良言
那么它的优点是能够节省空间上的浪费，同时也能够有向的访问每条边及每个节点，效率高。
自然如此高超的东西编程复杂度也就有点小高，但是其实也不难，本蒟蒻个人认为
跟建树的过程有点像。
我们先来看看建树的代码：
1. 建树的Code
int tot,pre[N],now[N],son[N];
//pre表示当前新加的边的前一条边，now表示以x点为起点的未加新边之前的最后一条边，son表示当前边所指向的后一个节点，tot表示当前边的数量，即编号
void add(int x,int y)
{
pre[++tot]=now[x]; //将当前新加边的前继赋值为当前边，同时tot先自增
now[x]=tot; //将当前点x连接的最后一条边赋值为当前边数量，即编号
son[tot]=y; //将当前编号边所指向的节点赋值为y
}
果然非常的绕，但实际上我们只要弄清楚什么是当前边，前继边，当前节点，后继点与编号就行了。
那么这里now数组所储存的当前边的编号一定是最后一条与当前点相连的边。
所以，我们可以知道，在使用这样的形式遍历树时，其实是倒序遍历，看看代码就清楚了。
2. 树的遍历Code
int tot,pre[N],now[N],son[N];
bool fl[N];
//N根据题目情况认定
void dfs(int w)
{
fl[w]=true; //将当前点标记为已遍历
for (int p=now[w];p;p=pre[p])
//这里从最后一条边开始遍历，注意根它是没有前驱，所以for的终止条件是p==0，每次将p赋值为它的前驱边
{
int t=son[p]; //当前边所连接的后驱节点
if (!fl[t]) //当前节点未被访问
dfs(t); //继续遍历
}
}
这里需要自己多行体会，本蒟蒻就不再多赘述了。
好的，我们来回归正题：链式前向星。
其实它的原理跟存树差不多，所以我们定一个结构体。
3. 链式前向星Code
struct Edge
{
int pre; //当前点所连接边的前驱边
int to; //相当于前文的son
int w; //这里多了个权值，很好理解
} edge[T]; //边的存储
int now[T]; //同上文的now
//T因题的数据范围而定
那么加边也大同小异。
4. 建立图Code
inline void add_edge(int u,int v,int w) //起止点与权值
{
edge[++tot].pre=now[u];
//now[u]表示u点当前边的最后一条边
edge[tot].to=v;
//当前边所连的点
edge[tot].w=w; //权值
now[u]=tot; //将当前u点所连接的最后一条边的序号更新
}
访问更不用说。
5. 图的遍历Code
struct Edge
{
int pre; //当前点所连接边的前驱边
int to; //相当于前文的son
int w; //这里多了个权值，很好理解
} edge[T]; //边的存储
int now[T]; //同上文的now
bool vis[N];
//T因题的数据范围而定
void dfs(int u)
{
for (int p=now[u];p;p=edge[p].pre)
{
int v=edge[p].to;
if (!vis[v]) dfs(v);
}
}
//同遍历树那里
好了，总结一下：
链式前向星每添加一条边就会更新now数组，使得now数组存放的总是最新添加的某点的出边，此出边的now总指向now数组之前存放的出边的序号。——仍然转自先前那位大佬，多有冒犯
所以说我们在遍历整个图时，是倒序遍历的。
②插曲结束&Dijkstra的回顾
好了，再次回到Dijkstra算法，我们知道，它的思路就是贪心，具体的做法[pascal]是这样的：
Var
i,j,u,v,min:longint;
min,u:longint; {min存储当前找到的边的最小值，u表示当前边通向的点}
vis:array[0..100] of boolean; {当前是否被访问}
dis:array[0..100] of longint; {最短距离}
G:array[0..100,1..100] of longint; {邻接表存图}
Begin
{读入及存图部分，省略}
for i:=1 to n-1 do
begin
min:=999999;
u:=0; {min,u初始化}
for j:=1 to n do
begin
if (vis[j]=false)and(min>dis[j]) then {如果当前点没被访问且小于当前找到的最短距离}
begin
u:=j; {更新点}
min:=dis[j]; {更新距离，便于下一次比较}
end;
end;
if u=0 then break; {如果没有找到新节点，退出}
vis[u]:=true; {标记为已访问}
for v:=1 to n do
if (u<>v)and(dis[u]+w[u][v]) then {点不能重合且小于当前最短距离}
dis[v]:=dis[u]+w[u][v]; {更新最短距离}
end;
End.
[毕竟不是专学Pascal的，写得不好请见谅]
其中我们发现这样一段代码：
for j:=1 to n do
begin
if (vis[j]=false)and(min>dis[j]) then {如果当前点没被访问且小于当前找到的最短距离}
begin
u:=j; {更新点}
min:=dis[j]; {更新距离，便于下一次比较}
end;
end;
这里就是在找当前没被访问的最短距离最小的点，每次找到一条边权最小的边，那么我们的做法就是很愚蠢的枚举，这时，我们想到了堆！！！
③优化！优化！堆的运用
堆其实就是优先队列，升级了一点，它就是便于我们快速地取出具有优先属性的元素，本蒟蒻不再赘述对堆的描述。
那么我们具体的做法就是，每找到一条能够更新的最短权值的边时，我们就将其丢入堆中，同时定义结构体规定其优先性，由于此时堆的结构变得复杂，我们还需要运算符重载。
注意此时要不仅记录当前最短路的数值，还要记录当前最短路到达的节点。
优化AC具体代码如下
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
#pragma GCC optimize(2)
#define ri register int //卡常数
#define T 4001
#define N 1001
using namespace std;
int t,n,tot;
struct Edge //定义链式前向星
{
int pre;
int to;
int w;
} edge[T];
int now[T];
int dis[N];
struct path //这就是关键的结构体
{
int pos,val;
//表示当前最短路到达的点 及 最短距离的值
bool operator < (const path &x) const //对'<'进行重载
{
return val>x.val; //这里就是指将最短距离从小到大排
//注意写法是：(element元素) (比较规则) x.(element元素);
} //运算符重载，有兴趣的神犇可以去了解
/*
具体格式如下：
(返回类型) operator (运算符) (const (结构体名称) &x) const
{
...; //具体代码，对其重载
}
*/
} ;
bool vis[N]; //标记当前节点是否被访问
void Dijkstra()
{
priority_queue<path> heap;
//定义一个path类型的大根堆，由于数据越大的越在堆上部，而运算符重载使得最短路越小的越大，所以最短路越小的越在上部
memset(dis,0x7f,sizeof(dis)); //dis数组初始化
dis[1]=0,heap.push((path){1,0});
//dis出发点赋值，以及结构体放入堆中的写法：(结构体名称){...}
//PS注意{}中的元素按顺序，别弄反了，同时这时不将vis赋值，不然直接退出while，自行体会
while (!heap.empty()) //堆非空
{
path u=heap.top(); //定义一个path的u，取出最短路点
heap.pop(); //取出来
if (vis[u.pos]) continue; //若当前最短路径所到达的点已被访问，continue
vis[u.pos]=true; //当前节点标记为已访问
for (int p=now[u.pos];p;p=edge[p].pre) //遍历
{
int v=edge[p].to; //取出它所连接的边
if (dis[v]>dis[u.pos]+edge[p].w) //比较
{
dis[v]=dis[u.pos]+edge[p].w; //更新
heap.push((path){v,dis[v]});
//注意当前已被修改，那么当前的点与其所匹配的最短距离也可能修改其它点的最短路，丢入堆中
}
}
}
}
inline void add_edge(int u,int v,int w) //建图
{
edge[++tot].pre=now[u];
edge[tot].to=v;
edge[tot].w=w;
now[u]=tot;
}
inline void read(int &x) //快读
{
x=0;int f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-f;ch=getchar();}
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;
}
int main()
{
read(t),read(n);
for (ri i=0;i<t;++i)
{
int u,v,w;
read(u),read(v),read(w);
add_edge(u,v,w),add_edge(v,u,w);
} //读入，注意是无向图，要加两次边
Dijkstra(); //链式前向星+堆 优化
printf("%d",dis[n]);
return 0;
}
好了，本篇博客到此结束，Dijkstra完成了它的优化，时间复杂度大大减少，应该是O((m+n)log n)的。
3. 如有不当之处请各位神犇及时指出！
上一篇： TIL 14：sprintf