2021 RoboCom 7-3 打怪升级 （dijkstra+floyd）（好题！题型：“双权值“+路径记录）

分析：这道题目我们首先要找到一个起点，使得这个起点到其他所有点的最大距离尽可能地小，所以我们只能分别以每个点作为原点跑一遍最短路，这样就可以求出来最佳原点，当然这个过程我们可以直接用floyd来实现。

剩下的就是我们用最佳原点跑一边dijkstra求一下满足题意的最佳路径即可，就是改一下dijkstra更新的条件以及加一个pre数组来记录一下路径。

用dijkstra来更新最优路径（），太帅了！

：经典else if   封神！

for(int i=1;i<=n;i++)
		{
			if(d[i]>d[begin]+w1[begin][i])//代价优先选择小的 
			{
				d[i]=d[begin]+w1[begin][i];
				w[i]=w[begin]+w2[begin][i];
				pre[i]=begin;
				q.push({d[i],i});
			}
			else if(d[i]==d[begin]+w1[begin][i])//在代价相同时优先选择武器价值高的 
			{
				if(w[i]<w[begin]+w2[begin][i])
				{
					w[i]=w[begin]+w2[begin][i];
					pre[i]=begin;
					q.push({d[i],i});
				}
			}
		}

ACcode: 

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef pair<int,int>PII;
long long f[N][N],w1[N][N],w2[N][N];
long long d[N],w[N],pre[N],st[N],tt;
bool vis[N];
int n,m,k;
void dijkstra(int x)
{
	priority_queue<PII,vector<PII>,greater<PII> >q;
	q.push({0,x});
	memset(d,0x3f,sizeof d);d[x]=0;
	while(!q.empty())
	{
		int begin=q.top().second;
		q.pop();
		if(vis[begin]) continue;
		vis[begin]=true;
		for(int i=1;i<=n;i++)
		{
			if(d[i]>d[begin]+w1[begin][i])//代价优先选择小的 
			{
				d[i]=d[begin]+w1[begin][i];
				w[i]=w[begin]+w2[begin][i];
				pre[i]=begin;
				q.push({d[i],i});
			}
			else if(d[i]==d[begin]+w1[begin][i])//在代价相同时优先选择武器价值高的 
			{
				if(w[i]<w[begin]+w2[begin][i])
				{
					w[i]=w[begin]+w2[begin][i];
					pre[i]=begin;
					q.push({d[i],i});
				}
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	memset(f,0x3f,sizeof f);
	memset(w1,0x3f,sizeof w1);
	memset(w2,-0x3f,sizeof w2); 
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		scanf("%lld%lld",&w1[u][v],&w2[u][v]);
		f[v][u]=f[u][v]=w1[v][u]=w1[u][v];w2[v][u]=w2[u][v];
	}
	for(int i=1;i<=n;i++) f[i][i]=0;
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
		f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	long long ans=0x3f3f3f3f3f3f3f3f;
	int x=0;
	for(int i=1;i<=n;i++)
	{
		long long t=0;
		for(int j=1;j<=n;j++)
			t=max(t,f[i][j]);
		if(t<ans)//记录最大距离的最小值 
		{
			ans=t;
			x=i;
		}
	}
	for(int i=1;i<=n;i++) pre[i]=i;
	dijkstra(x);
	printf("%d\n",x);
	int k;
	cin>>k;
	while(k--)
	{
		int t;
		scanf("%d",&t);
		tt=0;
		while(x!=t)
		{
			st[++tt]=t;
			t=pre[t];
		}
		printf("%d",x);
		for(int i=tt;i>=1;i--)
			printf("->%d",st[i]);
		if(tt)
			printf("\n%lld %lld\n",d[st[1]],w[st[1]]);
		else
			printf("\n%lld %lld\n",d[x],w[x]);
	}
	return 0;
}

over~