dijkstra模板及例题（最短路算法）

P2984 [USACO10FEB]Chocolate Giving S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Farmer John有B头奶牛(1<=B<=25000)，有N(2*B<=N<=50000)个农场，编号1-N，有M(N-1<=M<=100000)条双向边，第i条边连接农场R_i和S_i(1<=R_i<=N;1<=S_i<=N)，该边的长度是L_i(1<=L_i<=2000)。居住在农场P_i的奶牛A(1<=P_i<=N)，它想送一份新年礼物给居住在农场Q_i(1<=Q_i<=N)的奶牛B，但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物，然后再送给奶牛B。你的任务是：奶牛A至少需要走多远的路程？

这道题与上面那道题一模一样，小伙伴们可以自己尝试着做一下。

P2888 [USACO07NOV]Cow Hurdles S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目大意：Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。 显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。 奶牛的训练场中有 N (1 ≤ N ≤ 300) 个站台，分别标记为1..N。所有站台之间有M (1 ≤ M ≤ 25,000)条单向路径，第i条路经是从站台Si开始，到站台Ei，其中最高的栏的高度为Hi (1 ≤ Hi ≤ 1,000,000)。无论如何跑，奶牛们都要跨栏。 奶牛们有 T (1 ≤ T ≤ 40,000) 个训练任务要完成。第 i 个任务包含两个数字 Ai 和 Bi (1 ≤ Ai ≤ N; 1 ≤ Bi ≤ N)，表示奶牛必须从站台Ai跑到站台Bi，可以路过别的站台。奶牛们想找一条路径从站台Ai到站台Bi，使路径上最高的栏的高度最小。 你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

输出：牛从起点到终点的路径上的最高的栏的高度的最小值，如果无法到达输出-1.

解析：这个题可以用floyd，花费时间137ms，不过这里讲的是dijkstra（497ms），所以就用dijkstra算法(mlogn=2 * 10 ^ 5)。这里的最短路就是栏的高度，上面求最短路都是用到方程：dis[j] = min(dis[j],dis[t]+f[t][j]);而这里用到的是dis[j] = min(dis[j], max(dis[t] , f[t][j])).我们用这个方程并套上面的模板去做该题，然后很理所应当地T掉，mlogn复杂度再乘T，可得时间复杂度8 * 10 ^ 9，严重超时。所以这题就没得做了吗？

        当然不是。我们可以用二维d来存放一个点到另一个点的距离(记忆化)，用vis来查看该点是否做过dijjkstra，不过这个好像更像bellman-ford，不过也没什么大碍，因为这两个算法在堆优化的时候是基本一样的。

#include
#include
#include
#include
#include
#define N 310
#define M 50010
#define inf 0x3f3f3f3f 
using namespace std;
int n,m,T,cnt;
int ne[M],w[M],e[M],h[M],inque[N],d[N][N],vis[N];//用二维d来存储花费
//快读
inline int read() {
	int date=0,w=1;
	char c=getchar();
	while(c<'0' || c>'9') {
		if(c=='-') w=-1;
		c=getchar();
	}
	while(c>='0' && c<='9') {
		date=date*10+(c-'0');
		c=getchar();
	}
	return date*w;
}
//邻接表
void add(int u,int v,int wi)
{
    e[++cnt]=v;
    w[cnt]=wi;
    ne[cnt]=h[u];
    h[u]=cnt;
}

void dijkstra(int s)
{
    queueq;
    memset(inque,0,sizeof(inque));
    memset(d[s],inf,sizeof(d[s]));
    q.push(s);
    inque[s]=1;//先标记起点
    d[s][s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inque[u]=0;//取出来用就解除标记
        for(int i=h[u]; i; i=ne[i])
        {
            int v=e[i];
            if(d[s][v]>max(d[s][u],w[i]))
            {
                d[s][v]=max(d[s][u],w[i]);
                if(!inque[v])
                {
                    q.push(v);//进队就标记
                    inque[v]=1;
                }
            }
        }
    }
}

void print(int s,int t) 
{
    if(d[s][t]==inf)printf("-1\n");
    else printf("%d\n",d[s][t]);
}

int main()
{
    n=read(),m=read(),T=read();
    for(int i=1;i<=m;i++)
    {
        int si=read(),ei=read(),hi=read();
        add(si,ei,hi); 
    }
    for(int i=1;i<=T;i++)
    {
        int ai=read(),bi=read();
        if(!vis[ai]) dijkstra(ai);//判断是否以ai为起点走过
        print(ai,bi);//输出，因为inf要输出-1，干脆写了个函数
        vis[ai]=1;//记录以ai为起点走过了
    }
    return 0;
}

        强烈建议小伙伴们好好消化完dijkstra的算法思想及掌握两个模板后，独立完成以上的例题，不要急于求成，直接看题解，这样做毫无意义可言。

        希望我的文章能够对你有所启发，创作不易，希望你们能够动动小手点个赞，谢谢各位！