自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 21:44:06，当前版本为作者最后更新于2020-03-02 14:43:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

关于Floyd，它太慢了

关于spfa,它死了

关于dijkstra，还是用它吧

步入正题：

这道题，千万不要被题面所误导

题目大意：点u到点1的最短路+点1到点v的最短路

但是，您要是照着这个思路写代码的话，只能拿到50分，T了5个点

显然，这个做法不够优秀

进一步，我们发现，在第i头奶牛的行动中，肯定会经过1号点

所以，只要跑一边dijkstra就好了，把起点设为1

每当进行一次询问，就输出d[u]+d[v] （d[]记录最短距离）

//注释都在代码里了

上代码：（vector存图+dijkstra+堆优化）

//代码重在实用，不在华丽的操作 
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,t,d[50010],ans;
//n个节点，m条边，t次询问，d[]存最短距离，ans为每次询问的答案 
struct edge
{
	int to,cost;
};
vector<edge>G[50010];//vector存图 
typedef pair<int,int>P;//定义一个pair类型的P（只是为了写起来简单一点） 
void dijkstra(int s)//s为起点，在这道题里就是1 
{
	priority_queue<P,vector<P>,greater<P> >q;
	//一个P类型（pair）类型的优先队列  
	for(int i=1;i<=n;i++) d[i]=1e9;//赋初值1e9 
	d[s]=0;//自己到自己的距离是0 
	q.push(P{0,s});//加入队列等待处理 
	while(!q.empty())
	{
		P p=q.top();//取队首 
		q.pop();
		//声明一下：p.first代表的是一个距离，而p.second代表的是一个点， 
		//Tell一个不为人知的秘密， 
		//若把p.first设为一个点，而把p.second设为一个距离，
		//程序的速度就没有第一个优秀（亲测） 
		int v=p.second;//也是为了写起来简便一点， 
		if(d[v]<p.first) continue;//如果已经是一个最短距离了，continue； 
		for(int i=0;i<G[v].size();i++)//循环点v连接的所有点 
		{
			edge e=G[v][i]; 
			if(d[e.to]>d[v]+e.cost)//松弛操作，贪心思想 
			{
				d[e.to]=d[v]+e.cost;//更新d[e.to]的值 
				q.push(P{d[e.to],e.to});//重新加入到队列等待处理 
			}
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&t);
	while(m--)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		G[u].push_back(edge{v,w});//注意，这个图是一个无向图 
		G[v].push_back(edge{u,w});
	}
	dijkstra(1);
	//以1号点为起点进行dijkstra()，便可获得1号点到其它任意一点的最短距离 
	while(t--)
	{
		ans=0;
		int u,v;
		scanf("%d%d",&u,&v);
		ans=d[u]+d[v];//直接输出答案 
		printf("%d\n",ans);
	}
	return 0;//养成良好习惯 
}

这世界上不缺少什么水题，而是缺少发现水题的眼睛

看我写的这么认真，是否可以点个赞再走呢？